动态规划算法题目练习——91.解码方法

1.题目解析

题目来源：91.解码方法——力扣 

测试用例 

2.算法原理

 基础版本

1.状态表示

由于题目只要求返回第i个位置的可能情况，则只需要开辟n(n=s.size())个大小的dp表即可

2.状态转移方程

题目可知第i个位置可以单独解码也可以与前一个位置组合解码，所以两种情况都需要讨论，当满足单独解码就加上前i-1个位置所有的可能性即可，当也满足与前一个位置组合解码就再加上前i-2个位置的所有可能性即可

3.初始化

需要初始化开始两个位置的值，其中dp[0]只需要判断第一个字符s[0]是否为'0'即可，为0则不能解码，dp[0]=0，反之可以解码则dp[0]=1

但是需要注意dp[1]需要判断的它本身是否可以单独解码还要判断是否可以和前一个位置组合解码

4.细节处理

需要注意这种解法不能处理n为1时的情况，需要单独处理n=1时返回dp[0]的值

5.返回值

由于只用返回第i个位置的可能性，所以映射的下标就是n-1，最后返回dp[n-1]即可

 优化版本

1.状态表示

前面的基础版本中对于第二个位置的初始化有些多余，不如只用初始化第一个dp表的位置即可，所以这里使用虚拟位置来优化

由于多了一个虚拟位置，就需要创建dp(n+1)的dp表，第一个位置用作虚拟位置，此时对应的第i个位置映射的下标也为i，更加清晰

2.状态转移方程

这里主要讲解的是对于虚拟位置的值如何确定，首先dp[1]也就是原来的dp[0]，直接初始化即可，但是如果要借助状态转移方程初始化dp[2]的时候，需要用到虚拟位置的情况就是在组合解码时，，也就是dp[2] += dp[2-2]时，此时因为已经确定了dp[2-1]可以与dp[2]组合解码也就是说dp[2-1]!='0'，这时将dp[0]虚拟位置置为1即可

3.初始化

简化了之后只用初始化除虚拟位置的第一个位置即可

4.细节处理

dp表多了一个虚拟位置但是s字符串没有，所以需要在基础版本的情况下将s的映射-1

5.返回值

dp表多开了一个位置，直接返回dp[n]即可

3.实战代码

初始版本 

class Solution {
public:int numDecodings(string s) {int n = s.size();//dp表默认初始化为0 vector<int> dp(n);dp[0] = (s[0] != '0');//特殊处理边界情况if(n == 1){return dp[0];}//当前两个数字都可以单独编码则加一种情况if(s[0] != '0' && s[1] != '0'){dp[1] += 1;}//当前两位可以组合编码则多一种情况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];}}//返回第n个位置,映射下标为n-1return dp[n-1];}
};

优化版本 

class Solution {
public:int numDecodings(string s) {int n = s.size();vector<int> dp(n+1);//将新加入的位置置为1dp[0] = 1;//将原来的第一个位置的初始值右移dp[1] = (s[1-1] != '0');for(int i = 2;i <= n;i++){//当第i个位置可以单独解码则加上前i-1个位置的可能性//第i个位置的映射下标为i-1if(s[i-1] != '0'){dp[i] += dp[i - 1];}//当第i个位置可以与前一个位置组合解码则加上前i-2个位置的可能性//注意不能有前导0，所以t从10开始限制范围int t = (s[i-2] - '0')*10 + s[i-1] - '0';if(t >= 10 && t <= 26){dp[i] += dp[i-2];}}return dp[n];}
};