Combination & Permutation & DP Counting


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


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


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 *