Another classic DP problems.
Given a non-empty string containing only digits, determine the total number of ways to decode it.
1->A
2->B
…
How many ways can we decode a given string?

for problem that asked us: how many ways…, instead of print out all the ways that can decode. so that implied us to use dp

and the dp equation is:
dp[i] means the number of decode ways if we only got the first i+1 chars
dp[i] = dp[i-1] (if the i-1 th char is between 1 to 9) + dp[i-2] (if the i-2,i -1 th char is between 10 and 26)

first, based on this thought, the code implemented are as followed: but it’s overflowed

class Solution {
    public int numDecodings(String s) {
        
        if(s == null || s.length() == 0) return 0;
        
        int n = s.length();
        int[] dp = new int[n];
        
        dp[0] = s.charAt(0) == '0'?0:1;
        
        for (int i = 1; i < n; i++) {
            int oneDigit = Integer.valueOf(s.substring(i, i + 1));
            int twoDigit = Integer.valueOf(s.substring(i-1, i + 1));
            
            if (oneDigit >= 1 && oneDigit <= 9) {
                dp[i] += dp[i-1];
            }
            if (twoDigit >= 10 && twoDigit <= 26) {
                dp[i] += dp[i-2]; //when i == 1, here is out of range
            }
        }
        return dp[n-1];
    }
}

so instead of define dp[i] as the first i+1(for example: dp[0] as the decode ways of only first char), we define dp[i] as the first i chars, which actually makes it much easier to remember, and we only needs to initialize dp as the length of n+1.

but here comes the most hard to understand part: dp[0] = 1 instead of 0. but it’s right.

class Solution {
    public int numDecodings(String s) {
        
        if(s == null || s.length() == 0) return 0;
        
        int n = s.length();
        int[] dp = new int[n + 1];
        
        dp[0] = 1; //this is the trickest part: dp[0] should be 1 instead of 0, but that's doesn;t suitable for its meaning. but we should assign dp[0] with 1 because, jus thinking about the "12", so when i = 2, dp[2] = dp[1] + dp[0], so it should be 1+1 instead of 1+0. it's actually the based case of dp[i-2]
        dp[1] = s.charAt(0) == '0'?0:1;
        
        for (int i = 2; i <= n; i++) {
            int oneDigit = Integer.valueOf(s.substring(i - 1, i));
            int twoDigit = Integer.valueOf(s.substring(i - 2, i));
            
            if (oneDigit >= 1 && oneDigit <= 9) {
                dp[i] += dp[i-1];
            }
            if (twoDigit >= 10 && twoDigit <= 26) {
                dp[i] += dp[i-2];
            }
        }
        return dp[n];
    }
}