(动态规划)leetcode91:解码方法

题目

一条包含字母 A-Z 的消息通过以下方式进行了编码：

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

输入: “12”
输出: 2
解释: 它可以解码为 “AB”（1 2）或者 “L”（12）。
示例 2:

输入: “226”
输出: 3
解释: 它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。

思路

本题的分类讨论思路如下：
先初始化一个dp数组，dp[n]记录字符串的数目为n时解码方法的总数。

1.当s[i-1]不是“1”或“2”的时候，证明s[i]不可以和s[i-1]联合解码
1.1 当s[i]是 “0”的时候，s[i]无法解码，返回0；
1.2 当s[i]不是“0”的时候，s[i]位置独立解码，此时dp[i+1]=dp[i]。
2.当s[i-1]是“1”或“2”的时候，证明s[i]可以和s[i-1]联合解码
2.1 当s[i]是 “0”的时候，s[i]一定要与s[i-1]一起解码，此时dp[i+1]=dp[i-1]；
2.2 当s[i]不是“0”的时候
2.2.1 如果1≤s[i]≤6，则可以联合解码，dp[i+1]=dp[i-1]+dp[i]；
2.2.2 否则，还是不可以联合解码，s[i]独立解码，dp[i+1]=dp[i]。

代码

class Solution {
public:
    int numDecodings(string s) {
        if(s.empty()||s[0]=='0')//字符串为空或者字符串中只有一个0
        {
            return 0;
        }
        int n=s.size();//字符大小
        vector<int> dp(n+1,1);//初始化为1
        for(int i=1;i<n;i++)
        {
            if(s[i]=='0')
            {
                if(s[i-1]=='1'||s[i-1]=='2')
                {
                    dp[i+1]=dp[i-1];//小技巧，如果使用dp[i]，则左边会出现dp[i-2],当i=1时，会出现dp[-1]的情况，所以使用dp[i+1]
                }
                else
                { 
                    return 0;
                }
            }
            else
            {
                if(s[i-1]=='1'||s[i-1]=='2'&&s[i]>='1'&&s[i]<='6')
                {
                    dp[i+1]=dp[i-1]+dp[i];//为什么是这样的，举个小例子如1212，后两位变化，其有两种形式为12 12或者121 2.
                }
                else
                {
                    dp[i+1]=dp[i];
                }
            }
        }
        return dp[n];
        
    }
};

备注

1.初始化不能为0，因为dp[1]=1