Prompt: Let’s say that all alphabet letters can be encoded into a number. For example:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

Given a string of numbers, how many ways can we decode the string. For example, “11106” can be mapped into:

1. “AAJF” with the grouping (1 1 10 6)
2. “KJF” with the grouping (11 10 6)

Solution: This problem can be solved with top down DP. We can start with the original string and loop through all numbers from range 1 to 26. If the string starts with one number, we can proceed to the next state with the new string being the remaining string after removing the starting number. This method might be still too slow; it is possible to make it faster with the help of a memory dictionary that memorizes the number of decoded ways for a substring.