动态规划|【斐波那契数列模型 】|91.解码方法

题目

91. 解码方法

一条包含字母 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 只包含数字，并且可能包含前导零

题目解析

       题目中说，对26个字母进行编码，然后给定一个纯数字的字符串要进行解码，解码也就是反过来用数字取对应字母，另外给出了一些规则，题目中要我们注意06不能映射成F,6可以映射成F。要求返回数字解码方法的总数。

动态规划思路

1.状态表示

       创建一个dp表，题目要求从左往右，进行解码,所以dp表一定是一个一维数组，根据前面文章里面的题目，我们状态表示一般使用以i位置为起点或者以i位置为终点，这里我们使用以i位置为终点，题目问，解码方式，所以dp[i]就表示从0位置到i位置的解码方式。

2.状态转移方程。

     要表示dp[i]，i位置的解码有两种方式，一种是单独解码，一种是i和i-1解码然后再加上前i-1位置的解码方式,我们先分析前两种方式的解码

单独解码

成功

i位置的数是1到9，从0到i-1位置的解码总数方式的表示根据状态表示得出就是dp[i-1],i位置单独解码成功就是，在前面那些解码后的串后面统一加一个字符，结果显而易见还是dp[i-1]种，所以这种情况的状态转移方程dp[i]=dp[i-1]

失败

i位置的数是0,如果最后一个不能解码，就说明前面的解码的全部失败，因为我要的整个的解码方式，不是局部的解码方式，所以只要最后一个不能解码就会导致整个数字串解码失败，dp[i]=0

i和i-1解码

成功

这个两个组合成一个两位数解码，因为题目中说06不能解码，说明想要成功解码这个两位数必须是10到26的（包含10和26），同理i和i-1解码成功，相当于在从0到i-2位置解码方式后面同一加上一个i和i-1解码出来的字符，结果还是dp[i-2]种，dp[i]=dp[i-2].

失败

同理，一个解码失败，整个数字串都不会成功dp[i]=0

总的解码情况，应该是单独解码成功的情况加上组合解码成功的情况所以dp[i]=dp[i-1]+dp[1-2]

3.初始化

之前说过初始化就是为了填表的时候不越界，算i位置的时候要用到i-1和i-2所以我们要初始化dp[0]和dp[1],

dp[0]:表示只有一个数字，这个数字是0的话就解码失败也就是dp[0]=0,这个数字是1到9 的时候解码成功也就是dp[0]=1

dp[1]:表示有两个数字，两个数字的话就可以单独解码或者组合解码，第一种分别单独解码（两个都是1到9）的数字，第二种就是两个数字组合也可以解码

如果这两种都不可以解码，dp[1]=0

这两个只有一个可以解码，dp[1]=1

这两个都可以解码，dp[1]=2

4.填表顺序

求dp[i]的时候要先知道dp[i-1]和dp[i-2],所以很明显填表顺序是从左往右

5.返回值

返回值，看状态表示就行返回dp[s.length-1]

代码

知道字符数字，要向组合还得减去‘0’，比如 整形5=字符5-字符0->5='5'-'0'

int numDecodings(char* s)
{
   int n =strlen(s);
    //创建dp表
    int dp[1000] = { 0 };
    //初始化
    if(s[0]!='0')dp[0]+=1;
    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;
    //边界
   //if(n==2)return 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];
}

时间复杂度：O(n)

空间复杂度：O(n)