动态规划算法学习——解码方法

算法学习——解码方法"/>

动态规划算法学习——解码方法

一，题目

一条包含字母 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 位 的整数。

示例 1：

输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2：

输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

示例 3：

输入：s = "06"
输出：0
解释："06" 无法映射到 "F" ，因为存在前导零（"6" 和 "06" 并不等价）。

提示：

• 1 <= s.length <= 100
• s 只包含数字，并且可能包含前导零。

二，题目接口

class Solution {
public:int numDecodings(string s) {}
};

三，解题思路及代码

这道题目是用动态规划的方法来解的，动态规划的解题步骤如下：

1.创建dp表

在这里，我们string是一个一维的字符串，所以我们创建的dp表也是一维的并且创建的dp表的长度和string的长度一样。所以我们创建dp表如下：

 int  n = s.size();vector<int>dp(n);

 2.dp表的状态转移方程

        首先我们来确定一下dp表的状态转移方程。dp表的状态转移方程该如何表示呢？

首先我们在解答这种问题时采取的思路一般都是以i位置为结尾或者起点计算i位置的解码次数。我们这道题采取的便是以i位置为结尾统计该位置上的解码次数有多少次。

i位置上的解码方式 = dp[i].

第一种情况：当i位置上使用一个字母解码时：解码成功后，dp[i] = dp[i-1]。为什么呢？因为我在i位置上解码成功的话相当于在i位置上添加一个字符，添加一个后缀，解码的次数是不会受到当前位置影响的。所以解码的次数还是dp[i-1]。解码失败的话便是0。

第二种情况：当我在i位置结合前一次的字符使用两个字符解码时，解码成功后，我的解码方式便是dp[i-2]。原因还是和前面的方式一样，使用后两次的数字字符解码得到的字母字符也是唯一的。作为后缀也只有一个，解码方式的个数不受这两个字符解码方式的影响。解码失败的话便是0。

3.初始化

   初始化dp表的操作其实只有两次，一次是初始化dp[0]，一次是初始化dp[1]。如何初始化dp[0]呢？首先，我们要知道的是dp[0]只能解码一个字符，所以dp[0] == 0或者dp[0] == 1。

所以初始化操作如下：

初始化dp[0]:

dp[0] = s[0]!='0';//因为中包含的只能是数字1-9,//所以当我的字符不是'0'时便可以解码成功，初始化为1,反之初始化为0.

特殊情况处理：

 if(n == 1)//只有一个字符直接返回dp[0],防止越界。{return dp[0];}

初始化dp[1]:

 dp[1] = s[1] != '0';//一个字符解码int t  = (s[0]-'0')*10+s[1]-'0';//两个字符解码if(t>=10&&t<=26){dp[1]++;}

  4.填表

  经过上面的处理以后便可以开始填表了，填表下标从2开始。填表方式如下：
 

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

5.返回值

根据下标的映射关系，我们返回的便是dp[n-1]的值。

 return dp[n-1];

全部代码：

class Solution {
public:int numDecodings(string s) {int  n = s.size();vector<int>dp(n);dp[0] = s[0]!='0';//因为中包含的只能是数字1-9,所以当我的字符不是'0'时便可以解码成功，初始化为1,反之初始化为0.if(n == 1)//只有一个字符直接返回dp[0],防止越界。{return dp[0];}if(s[1]!='0')//一个字符解码{dp[1]+=dp[1-1];}int t  = (s[0]-'0')*10+s[1]-'0';//两个字符解码if(t>=10&&t<=26){dp[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];//返回值}
};

减少初始化次数方法-----在dp表上添加节点优化

现在操作如下：

class Solution {
public:int numDecodings(string s) {int  n = s.size();vector<int>dp(n+1);//添加一个位置dp[0] = 1;//为了得到正确结果初始化为1dp[1] = s[0]!='0';//代表s[0]位置上的解码数for(int i = 2;i<=n;i++){if(s[i-1]!='0')//一个字符解码{dp[i] += dp[i-1];}int t  = (s[i-1-1]-'0')*10+s[i-1]-'0';//两个字符解码if(t>=10&&t<=26){dp[i]+=dp[i-2];}}return dp[n];//返回值}
};