# Decode Ways

## Transitions

If

`s[i] = '0'`

, then invalid ways (0)If

`s[i] = '1'`

, then we can choose to take`s[i]`

as it is, or pair it with the next digit (no matter what, it will form a valid number)If

`s[i] = '2'`

, then we can choose to take`s[i]`

as it is, or pair it with the next digit as long as the next digit is from`'0'`

to`'6'`

Any other digits have to be taken as it is

## Top-down

Modelling the transitions as-is gives us:

We can then memoize the value of each recursive call by index `i`

.

## Bottom-up

To solve this problem using bottom-up, let's re-frame the problem. However, notice that we cannot use the prefix of the array. This is because if we were to use the prefix `s[:i+1]`

, we would need to look-ahead to `s[i+1]`

, which should not be available yet. So we can re-framing the problem using suffixes instead:

Given $[i, n)$, can we find out how many ways there are to form $s[i-1]$?

**Trick: **Implementing recurrence relations
If the recurrence relation looks like $dp(i) = dp(i - 1)$, then it must be processed from left to right using prefixes. If it looks like $dp(i) = dp(i + 1)$, then it must be processed from right to left using suffixes.

Looking at the example above, if we have index `i`

, then we can use the values computed from `i+1`

onwards to figure out how many ways there are to form `s[i:].`

This gives us the recurrence relation:

Notice that it looks very similar to the original recurrence as we are essentially doing the same operations.

We can also apply the $n$ state caching optimization, where $n = 2$.

Note that the default values of `s1`

and `s2`

are both derived from the two base cases we have, with `s1 = 1`

because `i = |s|`

and `s2 = 0`

because `i > |s|`

(out of bounds so no ways to form it).

Last updated