算法 c++ 【动态规划专栏】专题一：斐波那契数列模型--------4.解码方法

本专栏内容为：算法学习专栏，分为优选算法专栏，贪心算法专栏，动态规划专栏以及递归，搜索与回溯算法专栏四部分。 通过本专栏的深入学习，你可以了解并掌握算法。

博主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 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

{

//处理单独编码：

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];

}

};

推荐文章