【学会动态规划】第 N 个泰波那契数（4）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【学会动态规划】第 N 个泰波那契数（4）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态规划怎么学？

1. 题目解析

2. 算法原理

1. 状态表示

2. 状态转移方程

3. 初始化

4. 填表顺序

5. 返回值

3. 代码编写

写在最后：

动态规划怎么学？

学习一个算法没有捷径，更何况是学习动态规划，

跟我一起刷动态规划算法题，一起学会动态规划！

1. 题目解析

【学会动态规划】第 N 个泰波那契数（4）,学会动态规划,动态规划,算法

这道题目不难理解，就是根据题目给的字符串的数字，

然后解码成字母有多少种情况，然后注意有前导零的数字不能解码。

2. 算法原理

1. 状态表示

这道题目的状态表示其实就是，

dp[ i ] 位置代表什么，而 dp[ i ] 位置代表的是到第 i 个位置的时候解码方法的总数是多少？

2. 状态转移方程

状态表达式的求解方法就是根据最近的一步划分问题，

我们来分析一下，dp[ i ] 有两种解码方法，

1. s[ i ] 单独解码，如果是单独解码，当 s[ i ] 的值是 1~9 的时候可以自己解码，

自己解码的方案数就是 dp[ i - 1 ]，如果 s[ i ] 的值是 0，那方案数就是0，整体解码失败，

2. s[ i ] 和 s[ i - 1 ] 一起解码，当 s[ i - 1 ] * 10 + s[ i ] 的值是 10~26 的时候就可以解码，

而解码数就是 dp[ i - 2 ]，如果解码失败，不在这个区间内，那方案数就也是0。

所以我们可以得出转态转移方程大体是：

dp[ i ] = dp[ i - 1 ] + dp[ i - 2 ] （根据上面的方案数判断规则）

3. 初始化

初始化就是防止填表的时候越界，

而我们的状态转移方程需要用到 dp[ i - 1 ] 和 dp[ i - 2 ]，

所以我们要初始化 dp[ 0 ] 和 dp[ 1 ] 位置，

dp[ 0 ] 位置，如果s[ 0 ] 解码成功就是1，不成功就是0

dp[ 1 ] 位置，如果 dp[ 1 ] 能自己解码，就 + 1，如果能跟 dp[ 0 ] 一起解码，就再 + 1，

如果dp[ 1 ] 两种情况都不能解码，就是0。（所以可能是0, 1, 2）

4. 填表顺序

填表顺序还是从左往右。

5. 返回值

返回值就是字符串最后一个位置的方案数，dp[ s.size() - 1 ]。

3. 代码编写

class Solution {
public:
    int numDecodings(string s) {
        // 创建dp表
        int size = s.size();
        vector<int> dp(size);

        // 初始化
        dp[0] = s[0] != '0';
        if(size == 1) return dp[0];

        if(s[0] != '0' && s[1] != '0') dp[1]++;
        int tmp = (s[0] - '0') * 10 + (s[1] - '0');
        if(tmp >= 10 && tmp <= 26) dp[1]++;

        for(int i = 2; i < size; i++) {
            if(s[i] != '0') dp[i] += dp[i - 1]; // 单独解码
            tmp = (s[i - 1] - '0') * 10 + (s[i] - '0');
            if(tmp >= 10 && tmp <= 26) dp[i] += dp[i - 2]; // 和前面联合解码
        }
        return dp[size - 1];
    }
};