Core Concept

Probability DP (dynamic programming) computes expected values or probabilities instead of counts or extrema. Each dp value represents the probability or expected value at a position, and transitions have probabilities attached.

In standard DP, you might write $dp[i] = \min(dp[i-1] + cost_1, dp[i-2] + cost_2)$. In probability DP, you write $dp[i] = p_1 \cdot dp[i-1] + p_2 \cdot dp[i-2]$ where $p_1$ and $p_2$ are probabilities. The observation: instead of taking min or max, you take a weighted sum. Each transition contributes proportionally to how likely it is.