网站设计计划书,怎么建立自己企业网站,代发新闻稿最大平台,服务平台收件箱91. 解码方法 - 力扣#xff08;LeetCode#xff09; 在完成动态规划入门之后#xff0c;我们先整一个中档题#xff0c;也是前面简单题的变体。
分析思路#xff1a;
在拿到最终结果之前#xff0c;我们应该明确什么样的数字序列能够解码。
规则1#xff1a;由于只有…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();vectorint 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(num10 num26)dp[1] 1;//填表for(int i2;in;i){if(s[i] ! 0)dp[i] dp[i-1];int tmp (s[i-1] - 0)* 10 s[i] - 0;//保存这种情况代表的两位数if(tmp10 tmp26)dp[i] dp[i-2];} return dp[n-1];}
};
