南海网站建设报价百度后台登录

91. 解码方法 - 力扣（LeetCode）

在完成动态规划入门之后，我们先整一个中档题，也是前面简单题的变体。

分析思路：

在拿到最终结果之前，我们应该明确什么样的数字序列能够解码。

规则1：由于只有26个字母，所以如果是前后两位数字，必须要在1~26之间

规则2：单个0不能直接映射，例如03、05这种也不能映射，只有10和20才能够含有0

规则3：如果是单个映射那就只能在1~9之间，如果是两位数映射那么十位上只能是1或者2，如果是1的话，个位的范围是0~9，如果是2的话，个位的范围是0~6，也就是两位数在10~26之间

如果我们免去映射规则，那么这道题就退化成一次只能上一个或者两个台阶的题目了。所以这道题的区别就在于，有些台阶不能迈腿例如出现04，有些地方例如10或者20，只能迈两步不能迈一步，所以需要通过制定上面的规则来筛选出不能迈腿的地方，然后用台阶问题的模板解决。

接下里我们通过回答五个问题来逐步分析解题需要的过程。

1.状态表示什么

根据经验和题目要求，不难得到这道题的dp[i]可以表示为以i位置为结尾的解码方法的总数。我们一般先考虑从结尾向前，所以离结尾最近的一步有两种情况，据此写出状态转移方程。

2.状态转移方程

情况一：最后一步是单独解码，根据上面的规则可以知道，如果单独解码的数字在1~9之间则解码成功，否则解码失败不进行累加。

情况二：最后一步解码了两位数，根据上面的规则可以知道，如果两位数解码的数字在10~26之间则解码成功，否则解码失败不进行累加。

所以在两种情况都解码成功的情况下，状态转移方程为dp[i]=dp[i-1]+dp[i-2]

3.初始化

dp[0]：如果解码成功则为1，否则为0

dp[1]：情况一：单步和双步两种方法都解码失败，此时为0

情况二：单步和双步有一种成功一种失败，此时为1

情况三：单步和双步都解码成功，此时为2

4.填表顺序

根据状态转移方程可以知道：后面的值依赖前面的值，所以是从前往后填

5.返回值

按照dp[i]的定义可以知道，最后返回的就是dp[n-1]

具体实现：

class Solution {
public:int numDecodings(string s) {int n = s.size();vector<int> dp(n);//初始化dp[0] = (s[0] != '0');//先处理边界情况if(n == 1) return dp[0];//如果前两个数都不为0，就说明能单步解码if(s[0] != '0' && s[1] != '0')dp[1] += 1;int num = (s[0] - '0') *10 + s[1] -'0';//通过ASCII码转化来保存前两个位表示的数if(num>=10 && num<=26)dp[1] += 1;//填表for(int i=2;i<n;i++){if(s[i] != '0')dp[i] += dp[i-1];int tmp = (s[i-1] - '0')* 10 + s[i] - '0';//保存这种情况代表的两位数if(tmp>=10 && tmp<=26)dp[i] += dp[i-2];} return dp[n-1];}
};