40.解码方法（动态规划）

题目描述：

一条包含字母 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) 。

代码:

class Solution {
public:
    int numDecodings(string s) {
        int n=s.length();
        if(n==0||(n==1&&s[0]=='0'))
            return 0;
        if(n==1)
            return 1;
        int dp[n+1];
        dp[0]=1;
        for(int i=0; i<n; i++)
        {
            dp[i+1]=s[i]=='0'?0:dp[i];
            if(i>0&&(s[i-1]=='1'||(s[i-1]=='2'&&s[i]<='6')))
                dp[i+1]+=dp[i-1];
            
        }
        return dp[n];
    }
};

执行效率：

执行用时 :4 ms, 在所有 C++ 提交中击败了84.46%的用户

内存消耗 :8.5 MB, 在所有 C++ 提交中击败了18.04%的用户