Java版多解法《把数字翻译成字符串》

方法1： 递归：将大问题化解为小问题

public class Solution {
    public int solve (String nums) {
        return back(nums.toCharArray(), 0);
    }
    // 递归函数
    public int back(char[] nums, int start){
        //当start走到终点时，证明已经解码完毕，直接返回1
        if(start == nums.length){
            return 1;
        }    
        //当字符为0的时候，0没对应的解码，所以直接返回0 (此路解码废掉)
        if(nums[start] == '0')
            return 0;
        //每次解码一个字符
        int res1 = back(nums,start+1);
        int res2 = 0;

        //如果当前字符等于1 或者 当前字符加上下一个字符合起来小于等于26 则可以一次解码两个字符
        if((start < nums.length-1) && (nums[start] == '1' || (nums[start] == '2' &&nums[start+1] <= '6'))){
            res2 = back(nums,start+2);
        }
        //返回结果
        return res1 + res2;
    }
}

方法二： 动态规划
代码分析：

dp[i] 表示字符串nums中以i个位置结尾的前缀字符串的解码种数
例如 nums = "123", 此时dp[0]=1,dp[1]=2,dp[2]=3

分类讨论：

1. 当前字符不等于0的时候,dp[i] = dp[i-1],此时将当前位置的一个字符译码
2. 当前字符+前一个字符，记为num, 如果 10<=num<=26 此时符合两个合并一起译码的条件；
   • 若此时i等于1，直接dp[i]++;
   • 大于1, 则dp[i] += dp[i-2];
     • 举个例子： nums = "324"
     • 此时dp[0] = 1, dp[1]呢？ dp[2]呢？
     • 很明显nums[1] != '0'，所以dp[1] = dp[0],num = 32，此时不满足两个一起译码的条件则循环往下执行，此时 nums[2] != '0',则 dp[2] = dp[1] = 1, num = 24，此时满足两个一起译码的条件,因为i==2大于1，所以dp[2] += dp[2-2] ,dp[2] = 1+1 = 2。

总的来说，其实这道题目很像爬楼梯，一次能爬一层和爬两层，只是爬的过程中增加了一些限定条件，只要将这些限定条件屡清楚则可以完全搞懂这类题目~

public int solve (String nums) {
        if(nums.length() == 0 || nums.charAt(0) == '0')
            return 0;
        int[] dp = new int[nums.length()];
        dp[0] = 1;
        for(int i = 1; i < dp.length; i++){
            if(nums.charAt(i) != '0'){
                dp[i] = dp[i-1];
            }
            //  3 2 4 
            int num = (nums.charAt(i-1)-'0')*10 + (nums.charAt(i)-'0');
            if(num >= 10 && num <= 26){
                if(i == 1){
                    dp[i] += 1;
                }else{
                    dp[i] += dp[i-2];
                }
            }
        }
        return dp[nums.length()-1];

    }