Dynamic Programming21 sections · 916 units
Open in Course

Dice Roll Simulation - Problem Statement

Constrained sequences

Roll a die nn times. Face ii can appear at most rollMax[i]rollMax[i] times consecutively. Count valid sequences. State: dp[roll][face][consecutive]dp[roll][face][consecutive] = sequences after rollroll rolls, last face is faceface, with consecutiveconsecutive repeats. Transition: if new face differs, reset consecutive to 1.

If same face, increment consecutive (if within limit). improvement: instead of tracking consecutive, track dp[roll][face]dp[roll][face] = sequences ending with faceface. Subtract invalid extensions.