【动态规划打怪升级】——解码方法

一、动态规划练级攻略

• 1.状态表示（确定dp数组的含义）
  
• 2.状态转移方程（确定递推公式）
  
• 3.初始化
  
• 4.遍历顺序
  
• 5.返回值
  

二、解码方法

解码方法

思路：动态规划

• 1.确定状态表示（dp[i]的含义）
  dp[i]：以第i个位置为结尾的解码方法有dp[i]种。
  
• 2.确定状态转移方程（dp[i]等于什么）
  我们分析一下：
  
  

由状态表示，解码方式可分为：

1. s[i]单独解码
2. s[i] 和s[i-1]一起解码

如果是第一种情况，则s[i]有2种情况：

s[i]解码成功和s[i]解码失败。

（1）

如果s[i]解码失败，那么不管s[i]之前的解码是否成功，都全盘清空。所以当s[i]解码失败是，有0种方法。

（2）

如果s[i]解码成功，则dp[i] = dp[i-1]

因为如果s[i]解码成功，说明它之前的所有字符一定解码成功，则方法数就是dp[i-1]的方法数。这个类似于爬楼梯的问题，爬到第i层楼梯只有两种情况，第i-1层楼梯往上迈一步，或者第i-2层楼梯往上迈两步。方法数都是dp[i-1]或dp[i-2]。

那么解码成功的前提条件是：9 >= a >=1

以上是s[i]单独解码的情况。

以下是s[i]和s[i-1]一起解码的情况。

(1)如果s[i]和s[i-1]一起解码失败，那么即使s[i-1]之前都解码成功，总的解码方法数都是0。

(2)如果s[i]和s[i-1]一起解码成功，那么dp[i] = dp[i-2]。

那么解码成功的前提条件是：

10<= b*10 + a <= 26，b是十位上的数，所以需要乘10

注意这里是大于等于10，而不是大于等于1。

因为如果是大于等于1，会出现下面的情况：

注意题目要求，以0为前导的字符串是不能单独解码的。

所以状态转移方程为：

dp[i] = dp[i-1] + dp[i-2]

还有一个需要注意的点：

这里为什么是s[i]和s[i-1]共同解码，而不是s[i]和s[i+1]呢？

我们需要注意到，dp[i]的含义是：以i位置为结尾的解码方法数为dp[i]，当我们计算到s[i]位置时，后面的位置还没有考虑到，所以是s[i]与s[i-1]解码而不是s[i]与s[i+1]解码。

• 3.如何初始化
  由状态转移方程：dp[i] = dp[i-1] + dp[i-2]. 我们应该初始化dp[0]和dp[1].
  s[0]单独解码时，有成功和失败两种情况，所以dp[0] = 0/1；
  代码如下:

dp[0] = s[0] != '0'

s[0]和s[1]共同解码时，有以下情况：

（1）解码失败，也就是s[0]为前导0。dp[1] = 0

（2）s[0]!=‘\0’，此时会成功解码一次，dp[1] +=1

（3）10<= b*10 + a <= 26，说明此时可以共同解码，dp[1] +=1,此时dp[1] = 2;

代码如下：

//s[1] 和 s[0]一起解码的情况
if(s[0] !='0' && s[1]!='0')
     dp[1] +=1;//只要s[0]不是0，就可以解码一次
int t = (s[0] -'0')*10 + s[1] - '0' ; 
if(t >= 10 && t <= 26)//同时可以解码
     dp[1] +=1;

• 4.遍历顺序
  由状态转移方程可知，遍历顺序从左到右，且应该从i = 2位置开始遍历。
  
• 5.返回值
  返回dp[ n-1 ]即可。
  

具体代码如下：

class Solution {
public:
    int numDecodings(string s) 
    {
        //1.确定dp数组的含义
        //2.确定递推公式
        //3.如何初始化
        //初始化dp[0] = 0/1 和dp[1] = 0/1/2
        //4.如何进行遍历
        //5.返回值
        //字符串解码有两种情况1：s[i]单独解码，成功的话，dp[i] = dp[i-1];
        //2.s[i] 和 s[i-1]一起解码，如果((s[i-1]-'0')*10 + s[i]-'0') >=10 && ..<=26,解码成功，dp[i] = dp[i-2];
        //所以dp[i] = dp[i-1] + dp[i-2];
        int n = s.size();
        vector<int> dp(n);
        dp[0] = s[0] !='0';//单独解码的情况
        //s[1] 和 s[0]一起解码的情况
        if(s[0] !='0' && s[1]!='0')
            dp[1] +=1;//只要s[0]不是0，就可以解码一次
        int t = (s[0] -'0')*10 + s[1] - '0' ; 
        if(t >= 10 && t <= 26)//同时可以解码
            dp[1] +=1;            
        for(int i = 2;i<n;i++)
        {
            if(s[i] != '0')//单独解码，成功
                dp[i] += dp[i-1];
            int t = (s[i-1] -'0')*10 + s[i] - '0';
            if(t >= 10 && t <= 26)//第二种情况，解码成功
                dp[i] += dp[i-2];
        }
        return dp[n-1];
    }
};

时间复杂度O(n)，空间复杂度O(n)

总结

今天写了一道题解码方法的题目，比较难，但是也留下了印象。