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.
- 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
| Trick | Difficulty | |
|---|---|---|
| LC 1223. Dice Roll Simulation | DP Counting + Permutation + Consecutive Constraints | 5-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]
}