91. Decode Ways

A message containing letters from A-Z can be encoded into numbers using the following mapping:

‘A’ -> “1”
‘B’ -> “2”
…
‘Z’ -> “26”
To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, “11106” can be mapped into:

• “AAJF” with the grouping (1 1 10 6)
• “KJF” with the grouping (11 10 6)
  Note that the grouping (1 11 06) is invalid because “06” cannot be mapped into ‘F’ since “6” is different from “06”.

Given a string s containing only digits, return the number of ways to decode it.

The test cases are generated so that the answer fits in a 32-bit integer.

动态规划。转移方程的考虑比较麻烦。
当当前的字符不为0时，该为可以自己组成有效编码，因此dp[i] = dp[i-1]。
然后考虑上一位可以和当前位组成有效编码的情况，如果上一位和当前位的数字小于26，且上一位不等于0，则可以联合编码。
因此dp需要再加上前一位可以组成的编码数，即dp[i] += dp[i-2]。
当i等于1时，由于会越界因此我们手动给dp[i]++。

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if(s.charAt(0) == '0') return 0;
        int[]dp = new int[n];
        dp[0] = 1;

        for(int i = 1 ; i < n; i++){
            if(s.charAt(i) != '0'){
                dp[i] = dp[i-1];
            }
            if(s.charAt(i-1) != '0' && (s.charAt(i-1) - '0') * 10 + (s.charAt(i) - '0') <= 26 ){
                if(i > 1) dp[i] += dp[i-2];
                else dp[i]++;
            }
        }
        return dp[n-1];
    }
}