题解 | #把数字翻译成字符串#Java动态规划

思路：动态规划

1. 当前解码的可能情况为i-1或i-2时得到。 故dp定义dp[i]为前i个字符可能的编码数，dp[i] = dp[i-1] + dp[i-2]；
2. 特殊情况，当i和i-1组合成的数不在10 - 26范围时，只能由dp[i-1]得到。
3. 当dp[i]=0时，表示存在非法字符，直接返回0.

import java.util.*;


public class Solution {
    /**
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    public int solve (String nums) {
        // write code here
        char[] arr = nums.toCharArray();
        int n = arr.length;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = arr[0] != '0' ? 1 : 0;
        for (int i = 1; i < n; i++) {
            if (arr[i] != '0') {
                dp[i+1] = dp[i];
            }
            if (arr[i-1] == '1'
            || (arr[i-1] == '2' && arr[i] >= '0' && arr[i] <= '6')) {
                dp[i+1] += dp[i-1];
            }
            if (dp[i+1] == 0) return 0;
        }
        return dp[n];
    }
}