【爬台阶题型】剑指 Offer 46. 把数字翻译成字符串

剑指 Offer 46. 把数字翻译成字符串 - 力扣（LeetCode） (leetcode-cn.com)

这题 和 青蛙爬台阶是一样一样的。
一次爬一步，一次爬两步的区别
只不过，爬两步需要判断一下是否能爬而已其实和裴波那切公式一样

相关姐妹题型是 第91题。91. 解码方法

• 翻译的条件就是： 字符串的第i个位置

  • 如果i所在的位置可以 单独作为一位去翻译
  • 如果i所在的位置 和第i-1所在的位置元素 组成的数字在10，25之间也可以翻译。

用dp[i] 表示: 以第i位结尾的前缀串翻译的方案为 dp[i]

考虑第i位单独翻译 和 与前一位连接起来再翻译对dp[i]的贡献。

• 第i位 单独翻译 对dp[i]的 贡献为 dp[i-1]

• 如果第i-1 位存在，且 第i-1位和第i位形成的数字x 满足10<=x<=25

  • 可以把第i-1位 和 第i位连接起来翻译，对dp[i]的贡献为dp[i-2]

举例：

• 如果是1245， 第i位 5 只能选择单独翻译，为什么？ 因为如果和前面一位 组合起来就是45 ，远远超过10,25的范围。

  • 那么dp[i] dp[4] （5） 以第4位结尾的前缀串“1245”的方案数量 和 dp[3]以第三位结尾的前缀串 “124” 的方案数量 是一样的。

    • 这么说比较难以理解，这么理解：

    • dp[4] 可以怎么转化呢？ 他只能由前面一位推出来。因为当前这一位他不能组合！

    • dp[4] 只能由dp[3]推出来！！ 所以dp[4]=dp[3]

    • 假设一下：

      • 124
        假设有3种组合
            第一种组合  1 2 4   
            第二种组合  12 4 
            第三种组合  1 24
        这个时候来了X
        X不能和4组合
        124X
            第一种组合 1 2 4 X
            第二种组合 12 4 X
            第二种组合 1 24 X  
        还是这三种，不能多一种，因为没法组合
        

        • 之前理解岔劈了，以为是每个元素，其实是组成这个的总体个数

  • 也就是说dp[3]以第三位结尾的前缀串 124 假设他的方案是 3种。那么第4位结尾，

• 如果是1215, 第i位 5 可以选择单独翻译，也可以选择和前面一位组合翻译。

  • 分为两种情况了，组合与不组合
  • 也可以这么理解： dp[4] 可以由dp[3]推出 （不组合） 也可以由dp[2]推出（组合）
  • 那么dp[4] = dp[3]+dp[2]

初始化：dp[0]=1

为什么dp[0]=1 ?

• 因为dp[1]=1 字符串只有1位的时候，肯定为1，那么dp[i]=dp[i-1] dp[0]必然为1

class Solution
{
    public int translateNum( int num )
    {
        char[] ch = String.valueOf(num).toCharArray();
        int len = ch.length;
        int[] dp = new int[len+1];
        dp[0]=1;
        dp[1]=1;

        for(int i=2 ;i<=len;i++)
        {
            // 把当前这一位和前面一位组合成数字， 因为ch数组是从0开始，因此当前位是i-1 前一位是i-2
            int n =(ch[i-2]-'0')*10 +(ch[i-1]-'0');
            // 能组合
            if(n>=10&&n<=25)
            {
                dp[i]=dp[i-1]+dp[i-2];
            }
            // 不能组合
            else
            {
                dp[i]=dp[i-1];
            }
        }
        return dp[len];
    }
}