Combination & Permutation & DP Counting

Summary

A majority of DP counting problems would define a rule of combination or permutation, under which, you have to calculate the total number of different combinations or permutations.

Some typical rules and corresponding solutions are listed below.

  1. At most x same consecutive elements; the solution is to use a dimension to record the consecutive elements or handle them while transfer states

OJ

 TrickDifficulty
LC 1223. Dice Roll SimulationDP Counting + Permutation + Consecutive Constraints5-6 points

Details

LC 1223. Dice Roll Simulation

We handle the consecutive constrains while transferring states.

// each i will start a new consecutive sequence with length 1 to rollMax[j]
// starting a new sequence means j will differ from prev
alg[i][prev] = sum {
   alg[i + k][j] for k in [1, rollMax[j]] for j != prev && j in [1, 6]
}

Leave a Reply

Your email address will not be published. Required fields are marked *