Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 91 Decode Ways - Transition

Two choices

At position ii: If s[i]s[i] is '00': dp[i]=0dp[i] = 0 (can't decode) Otherwise: dp[i]=dp[i+1]dp[i] = dp[i+1] (take one digit) If s[i..i+1]s[i..i+1] forms 1010-2626: dp[i]+=dp[i+2]dp[i] += dp[i+2] (also take two digits) The total is the sum of both valid choices.

The transition defines how the answer for the current state depends on answers for previous states. Notice that dp[i]dp[i] only looks at dp[i+1]dp[i+1] and dp[i+2]dp[i+2], so you fill the table from right to left.