AlgoScope

Decode Ways

ways[i] adds ways[i-1] when the digit is not 0 and ways[i-2] when the pair before it lies in 10..26.

Dynamic programming, algorithm, intermediate
ways at 1 is 1.012345digitways1110611
ways at 1 is 1.012345digitways1110611

DP in One Row: Decode ways of 11106

Decision, step 2 of 7

Digit 1 is 1. Alone it is letter A, so add ways[0] = 1. There is no digit before it for a pair. ways[1] = 1.

How dp in one row works

Cost

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)

Taught by the same lesson

DP in One Row covers these too, in the same run.