一、动态规划练级攻略
- 1.状态表示（确定dp数组的含义）
- 2.状态转移方程（确定递推公式）
- 3.初始化
- 4.遍历顺序
- 5.返回值
二、解码方法
思路：动态规划
- 1.确定状态表示（dp[i]的含义）
dp[i]：以第i个位置为结尾的解码方法有dp[i]种。 - 2.确定状态转移方程（dp[i]等于什么）
我们分析一下：
由状态表示，解码方式可分为：
- s[i]单独解码
- 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)
总结
今天写了一道题解码方法的题目，比较难，但是也留下了印象。
