A message of digits is encoded where 'A'→1 … 'Z'→26. Given a digit string, count how many ways it can be decoded. e.g. '226' → 3 ('2 2 6', '22 6', '2 26'). Leading zeros are invalid.
A Fibonacci-shaped 1D DP with guard conditions — the tricky part is validating one- and two-digit takes, especially zeros.
This is climbing-stairs with validity rules: dp[i] = number of ways to decode the prefix of length i. From position i you can consume one digit (valid only if it is 1–9), contributing dp[i-1], or two digits (valid only if the pair is 10–26), contributing dp[i-2]. Base cases dp[0] = 1 (empty) and dp[1] = (s[0] is not '0'). The zero is the whole trap: a '0' has no single-digit decoding and is legal only as the second digit of 10 or 20, so an isolated or badly placed 0 zeroes the count. Recognition signal: 'count the number of ways to build/parse a sequence one or two steps at a time' → additive DP dp[i] = dp[i-1] + dp[i-2] gated by which steps are legal here. Only the last two values are ever needed, so O(1) space.
Counting decodings/tilings/step-sequences where each move consumes 1 or 2 units under validity rules → gated Fibonacci-style dp[i] = (valid1 ? dp[i-1] : 0) + (valid2 ? dp[i-2] : 0).
Time O(n) · Space O(1)