题解 | #把数字翻译成字符串#TOP69

思路:
1.递归思想
2.ABCDEFG，如果D是0,A不是1和2，那么ABCD无法组合，不能出现30 40 这样的组合。如果A是1或2,10 20 是被允许的，那么组合只能是(AB)(CD) 不考虑AB组合的多少。所以利用dp[i] 来代表第i个位置的组合数量，A是1或2 就为 dp[i] = dp[i-2]
3.如果D是1到6，那么如果C是1到2，是不是可以写成(AB)(CD) 或者(ABC)(D) ,公式就是dp[i] = dp[i-2]+dp[i-1],如果C是3到9，那么只能是(ABC)(D) ，dp[i] = dp[i-1]
4.如果D是7到9，那么C是1的话，组合可以是(ABC)(D)或者(AB)(CD) ,公式 dp[i] = dp[i-1] +dp[i-2],C是2到9，那么只能是(ABC)(D) dp[i] = dp[i-1];

public class Solution {
    /**
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    public int solve (String nums) {
        // write code here
        if (nums == null || nums.length() == 0 ) {
            return 0;
        }
        //dp[i] 表示字符串nums中以i位置结尾的前缀字符串的解码种数
        //一种情况是第i位可以独立编码，另一种情况是第i位可以和第i-1位字符组合进行编码
        int[] dp = new int[nums.length() ];
        //dp[0] = 1;
        //第一个数是0 则没有编译的可能
        dp[0] = nums.charAt(0) == '0' ? 0 : 1;


        for (int i = 1; i < nums.length(); i++) {
            if (nums.charAt(i) == '0') {
                //xxx0 只能组合走，强制要前面一个数配合
                if (nums.charAt(i - 1) == '1' || nums.charAt(i - 1) == '2') {
                    if (i == 1) {
                        dp[i] = 1;
                    } else {
                        dp[i] = dp[i - 2];
                    }
                } else {
                    return 0;
                }
            } else if (nums.charAt(i) >= '1' && nums.charAt(i) <= '6') {

                //xx1  xx2   既可以单独作为一种编码，也可以和前面一个数作为一种编码组合
                if (nums.charAt(i - 1) == '2' || nums.charAt(i - 1) == '1') {
                    if (i == 1) {
                        dp[i] = 2;
                    } else {
                        dp[i] = dp[i - 1] + dp[i - 2];
                    }
                } else {
                    //不可能是 31 32  等，所以只能是一种编码方式，单独
                    dp[i] = dp[i - 1];
                }

            } else {
                //7 - 9 xx7
                if (nums.charAt(i - 1) == '1') {
                    if (i == 1) {
                        dp[i] = 2;
                    } else {
                        dp[i] = dp[i - 1] + dp[i - 2];
                    }
                } else {
                    dp[i] = dp[i - 1];
                }

            }
        }
        return dp[nums.length() - 1];
    }
}