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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    public int solve (String nums) {
        // write code here

        // 算法核心思想：从0到n，以n为出口的记忆化搜索

        // dp[i] - 表示从第i字符到结尾，总共有dp[i]种译法
        int[] dp = new int[nums.length() + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = -1;
        }


        return process(nums, 0, dp);
    }

    public int process (String nums, int i, int[] dp) {
        int n = nums.length();
        // 递归出口
        if (i == n) {
            dp[i] = 1;
            return dp[i];
        }

        // 递归分支
        if (dp[i] != -1) {
            return dp[i];
        }
        // 可以只译当前一位数，也可以尝试译两位数

        // 先尝试只译一位数
        int num = Integer.parseInt(nums.substring(i, i + 1));
        int one = 0;
        if (num != 0) {
            // 注意非0
            if (dp[i + 1] == -1) {
                dp[i + 1] = process(nums, i + 1, dp);
            }
            one = dp[i + 1];
        }

        // 再尝试译两位数
        int two = 0;
        if (i < n - 1 && num != 0) {
            // 确保不越界，且不以0开头
            num = Integer.parseInt(nums.substring(i, i + 2));
            if (num > 0 && num <= 26) {
                // 合法字母
                if (dp[i + 2] == -1) {
                    dp[i + 2] = process(nums, i + 2, dp);
                }
                two = dp[i + 2];
            }
        }

        // 计算结果
        dp[i] = one + two;
        return dp[i];
    }
}