响应式网站管理,网站建设与开发定制,百度地图轨迹导航,我们做网站 老公弟弟也跟着做1.题目解析 题目来源#xff1a;91.解码方法——力扣 测试用例 2.算法原理 基础版本 1.状态表示 由于题目只要求返回第i个位置的可能情况#xff0c;则只需要开辟n(ns.size())个大小的dp表即可 2.状态转移方程 题目可知第i个位置可以单独解码也可以与前一个位置组合解码91.解码方法——力扣 测试用例 2.算法原理 基础版本 1.状态表示 由于题目只要求返回第i个位置的可能情况则只需要开辟n(ns.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时的情况需要单独处理n1时返回dp[0]的值 5.返回值 由于只用返回第i个位置的可能性所以映射的下标就是n-1最后返回dp[n-1]即可 优化版本 1.状态表示 前面的基础版本中对于第二个位置的初始化有些多余不如只用初始化第一个dp表的位置即可所以这里使用虚拟位置来优化 由于多了一个虚拟位置就需要创建dp(n1)的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 vectorint 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();vectorint dp(n1);//将新加入的位置置为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];}
};
