[数据结构与算法]2021.8.22 力扣-解码方法

题目描述：

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

方法一：

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> f(n+1);
        f[0] = 1;
        for (int i = 1; i <= n; i++)
        {
            if (s[i - 1] != '0')
            {
                f[i] += f[i - 1];
            }
            if (i > 1 && s[i - 2] != '0' && (s[i - 2] - '0') * 10 + (s[i - 1] - '0') <= 26)
            {
                f[i] += f[i - 2];
            }
        }
        return f[n];
    }
};

这题原本用的是dfs回溯，但是会超时，瞄了一下题解，发现是用动态规划，可惜貌似还从未正经地使用过动态规划的方法，于是还是直接看题解吧。

设f[i]为前i个数字可以解码的方法总数(即0,1,2.....i-1)。求解f[i]的过程为：在已经确定前i-1个数字可以解码的方法总数的情况下，加入第i个数字s[i-1]后有两种情况：

①s[i-1]不为0，那么s[i-1]本身就可以映射一个字母，所以f[i]至少等于f[i-1]；

②s[i-2]不为0，而且10*s[i-2]+s[i-1]小于等于26，那么10*s[i-2]+s[i-1]可以映射一个字母，所以f[i]至少等于f[i-2]。

将以上两种情况加起来就是f[i]的值。

动态规划还是挺重要、有用、有趣的方法的，我决定接下来专门练一下动态规划的题目。