Formula: dp[n]=dp[n-1]+dp[n-2]

Bottom-up solution:

dp[i], i stand for the number of characters in the string.

Base case: dp[0] = 1. reason: after we look back to i-2 OR i-1, there's no characters left in the string. So it's valid case.

Similarly for dp[1] , when we look back, there's 1 character which is the first character in the string, we then check if this character is valid.

```
public class Solution {
public int numDecodings(String s) {
if(s == null || s.length() == 0) return 0;
int[] dp = new int[s.length()+1];
dp[0] = 1;
dp[1] = (s.charAt(0) == '0')? 0 : 1;
for(int i = 2; i<= s.length(); i++)
{
// check if s.substring(i-2,i) valid
int val = Integer.parseInt(s.substring(i-2, i));
dp[i] = (val >= 10 && val <= 26)? dp[i-2]: 0;
// check if s.substring(i-1, i) valid
val = Integer.parseInt(s.substring(i-1, i));
dp[i] += (val == 0) ? 0 : dp[i-1];
}
return dp[s.length()];
}
```

Time Complexity: O(n) , Space Complexity : O(n)