本专栏内容为:算法学习专栏,分为优选算法专栏,贪心算法专栏,动态规划专栏以及递归,搜索与回溯算法专栏四部分。 通过本专栏的深入学习,你可以了解并掌握算法。
💓博主csdn个人主页:小小unicorn
⏩专栏分类:动态规划专栏
🚚代码仓库:小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识
专题一
- 题目来源
- 题目描述
- 题目解析
- 算法原理
- 1.状态表示
- 2.状态转移方程
- 3.初始化
- 4.填表顺序
- 5.返回值
- 代码实现
题目来源
本题来源为:
Leetcode91. 解码方法
题目描述
一条包含字母 A-Z 的消息通过以下映射进行了 编码 :
‘A’ -> “1”
‘B’ -> “2”
…
‘Z’ -> “26”
要解码已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,“11106” 可以映射为:
“AAJF” ,将消息分组为 (1 1 10 6)
“KJF” ,将消息分组为 (11 10 6)
注意,消息不能分组为 (1 11 06) ,因为 “06” 不能映射为 “F” ,这是由于 “6” 和 “06” 在映射中并不等价。
给你一个只含数字的 非空 字符串 s ,请计算并返回解码 方法的总数 。
题目数据保证答案肯定是一个 32 位 的整数
题目解析
解码按照规则解码即可,但是前导0不可解码。
算法原理
1.状态表示
经验+题目要求:
以i位置为结尾…
对于本题而言就是:
dp[i]表示:以i位置为结尾时,解码方法的总数
2.状态转移方程
在推方程之前,我们先画一下解码的情况:
分为单独解码和与前一个位置一起解码两种情况:
而单独解码和一起解码又要分为两种情况,成功和失败。
为什么会失败呢?
举个例子:
2和5可以一起解码,也可以分开解码,但到0位置时,就会解码错误,自己单独不能解码,要是与后面的6结合,
会出现之前说的前导0情况,也会解码错误。
因此,本题的状态转移方程为:
dp[i] = dp[i-1]+ dp[i-2]
3.初始化
本题初始化要在下标为0位置与下标为1位置进行初始化:
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;
4.填表顺序
根据状态转移方程,我们计算dp[i]位置的值需要i-1与i-2位置的值,因此我们的填表顺序为:从左往右
5.返回值
我们要解码到最后一个位置,因此:返回dp[n-1]
代码实现
class Solution
{
public:int numDecodings(string s) {// 1.创建dp表// 2.初始化// 3.填表// 4.返回值int n=s.size();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];}return dp[n-1];}
};