BM69 #把数字翻译成字符串# 动态规划 + 逆序遍历（简单易懂！）

import java.util.*;
public class Solution {
    public int solve (String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[n] = 1; // 当字符串为空时，有一种解码方式
        dp[n - 1] = s.charAt(n - 1) != '0' ? 1 : 0; // 最后一个数字如果不是0，则有一种解码方式
        // 逆序遍历，便于处理前导0
        for (int i = n - 2; i >= 0; i--) {
            if (s.charAt(i) == '0') continue; // 当前数字如果为0，则跳过，因为0不能单独解码
            int num = Integer.parseInt(s.substring(i, i + 2)); // 检查两位数的可能性
            if (num <= 26) {
                dp[i] = dp[i + 1] + dp[i + 2]; // 如果两位数合法，则当前解码数为后两位的解码数之和
            } else {
                dp[i] = dp[i + 1]; // 否则，只考虑一位数的情况
            }
        }
        return dp[0];
    }
}