leetcode 91 java

LeetCode 91题是一道非常经典的动态规划问题，题目名为"解码方法"（Decode Ways）。给定一个只包数字的非空，求解有多少种解码方式具体来说给定的字符串由数字字符组成，可以解码成字母。规定字母'A'对应数字1，字母'B对应数字2，以此类推，字母'Z'对应数字26。现在要求计算出给定字符串的所有可能的解码方式数量。

解决这个问题的一种常见方法是使用动态规划。我们可以定义一个长度为n+1的数组dp，其中dp[i]表示字符串的前i个字符的解码方式数量。根据题目要求，我们需要考虑以下几种情况：

1. 如果当前字符为0，那么它不能单独解码，必须与前一个字符组合起来解码。如果前一个字符为1或2，那么可以将当前字符与前一个字符组合起来解码，即dp[i] = dp[i-2]；否则，无法解码，返回0。
2. 如果当前字符不为0，那么它可以单独解码成一个字母，即dp[i] = dp[i-1]。同时，如果前一个字符和当前字符组合起来可以解码成一个字母（范围在1到26之间），那么也可以将前两个字符一起解码，即dp[i] += dp[i-2]。

最终，我们可以通过遍历字符串的每个字符，更新dp数组的值，最后返回dp[n]即可得到解码方式的数量。

下面是Java语言的示例代码：

public int numDecodings(String s) {
    int n = s.length();
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = s.charAt(0) == '0' ? 0 : 1;
    
    for (int i = 2; i <= n; i++) {
        int oneDigit = Integer.parseInt(s.substring(i - 1, i));
        int twoDigits = Integer.parseInt(s.substring(i - 2, i));
        
        if (oneDigit >= 1 && oneDigit <= 9) {
            dp[i] += dp[i - 1];
        }
        
        if (twoDigits >= 10 && twoDigits <= 26) {
            dp[i] += dp[i - 2];
        }
    }
    
    return dp[n];
}