【动态规划】【爬台阶题型】 91. 解码方法

91. 解码方法 - 力扣（LeetCode） (leetcode-cn.com)
此为剑指 Offer 46. 把数字翻译成字符串 姐妹题

爬台阶题型：

• 【509. 斐波那契数】
• 【62. 不同路径】
• 【63. 不同路径 II】
• 【70. 爬楼梯】
• 【剑指 Offer 46. 把数字翻译成字符串】

其中第2个关于dp[i]的定义要注意：

• dp[i]: 字符串的前i个字符能形成的解码方案

• 比如：s="826".

  • 这个时候先看8， 则s所能形成的解码方案 就是 1 种

  • 这个时候如果在加1 位，就是s="82"，即hb, 数字82只能形成hb这个组合，

    • 同时也可以看出，因为dp[0]=1 所以dp[1]=dp[0]=1 ,
    • 表示s=“8”的时候，只有一个解码方案就是 h。
    • 再看s="82",根据dp[2] =dp[1]可以得到 s="82" 也只有一种解码方案

  • 突然来了个6 在看s="826"

    • 我们知道26可以解码为z,那么这个s=826有两种解码方案，即 hbf 和 hz
    • [8,2,6] [8,26] 不可能组成 [82,6]这第三种了，因为超过26了
    • 根据dp[i]= dp [i-1] ,dp[i]+=dp[i-2]
    • 先计算dp[3]=dp[2] ,dp[2]已经得出是1， dp[3]也是1.，这时候再根据dp[3]+=dp[1]
    • dp[3]=dp[3]+dp[1]=1+1= 2
    • dp[3]=2

class Solution {
    public int numDecodings(String s) {
        int n =s.length();
        // 注意：必须得是" "，有个空格，不能是""
        s=" "+s;
        char[] ch = s.toCharArray();
        int[] dp = new int[n+1];
        dp[0]=1;
        for(int i=1;i<=n;i++)
        {
            // 单独取一个数
            int a=ch[i]-'0';
            //取两个数，看一看是否能组合
                // 因为前面补了 “ ” ,字符从1开始，所以此处不是 (ch[i-2]-'0')*10 +(ch[i-1]-'0');
            int b=(ch[i-1]-'0')*10 +(ch[i]-'0');

            if(a>=1&&a<=9)
            {
                dp[i]=dp[i-1];
            }
            // 如果当前下标i只能和前面一个数组合。
            /*
                例如： 12
                    [1,2] [12]
                    突然来了个7 -> 127
                    也只能 两种
                    [1,2,7] [12,7]  不可能会有[1,27] 因为27超出范围了

            */

            if(b>=10&&b<=26)
            {
                dp[i]=dp[i-2];
            }
            // 如果既符合 a 有符合b ，那么就是说当前值可以由前一位推出，也可以由前两位推出。那么肯定+1；
            if(a>=1&&a<=9&&b>=10&&b<=26)
            {
                dp[i]= dp[i-1]+dp[i-2];
            }

        }
        return dp[n];
    }
}