动态规划专训1——泰波那契数列模型

动态规划的思想：将一个问题分隔为若干个子问题，完成子问题得到结构再得到最终的答案

动态规划往往解题步骤固定，分为以下几步

1.找出状态表示

2.完成状态转移方程

3.初始化

4.填表顺序

5.返回值

后面三步偏重细节，二解题的核心就在于前两步，所以要想练好动态规划，大量的练习，见识更多的题型无疑是很重要的，下面我们开始今天的练习

1.第N个泰波那契数

1137. 第 N 个泰波那契数

泰波那契序列 Tn 定义如下： 

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值

这道题目很简单，旨在让我们熟悉动态规划的解题步骤，下面我们展开分析

1.状态表示：用dp[ i ]表示第 i 个泰波那契数

2.状态转移方程：dp[ i ] = dp[ i – 1 ] + dp[ i – 2 ] + dp[ i – 3 ]

3.初始化：dp[0] = 0; dp[1] = 1; dp[2] = 1

4.填表顺序：从左往右依次填

5.返回值：dp[n]

当然我们要注意边缘数据的特殊处理，不然会出现越界的情况

class Solution {
public:
    int tribonacci(int n) 
    {
        //1. 创建dp表
        //2. 初始化
        //3. 填表
        //4. 返回值

        //边缘数据处理
        if(n == 0 || n == 1) return n;
        if(n == 2) return 1;

        vector<int> dp(n + 1);
        dp[0] = 0; dp[1] = 1; dp[2] = 1;
        for(int i = 3; i <= n; ++i)
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];

        return dp[n]; 
    }
};

这是ac代码

2.三步问题

面试题 08.01. 三步问题

三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007

1.状态表示：用dp[ i ]表示上到第i个台阶的可能方式

2.状态转移方程：dp[ i ] = dp[ i – 1 ] + dp[ i – 2 ] + dp[ i – 3 ]

3.初始化：dp[0] = 0; dp[1] = 1; dp[2] = 1

4.填表顺序：从左往右依次填

5.返回值：dp[n]

这里要注意数据的处理，因为数据很大，每一次相加之后都要对题给数据取模

class Solution {
public:
    int waysToStep(int n) 
    {
        const int MOD = 1e9 + 7;
        if(n == 1 || n == 2) return n;

        vector<int> dp(n + 1);
        dp[0] = 1; dp[1] = 1; dp[2] = 2;
        for(int i = 3; i <= n; ++i)
            dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + + dp[i - 3]) % MOD; 

        return dp[n]; 
    }
};

这是ac代码

3.使用最小花费爬楼梯

LCR 088. 使用最小花费爬楼梯

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当爬上一个阶梯都要花费对应的体力值，一旦支付了相应的体力值，就可以选择向上爬一个阶梯或者爬两个阶梯。

请找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯

1.状态表示：用dp[ i ]表示上到第i个阶梯需要的最小费用

2.状态转移方程：dp[i] = min(dp[i – 1] + cost[i – 1], dp[i – 2] + cost[i – 2])

3.初始化：dp[0] = 0; dp[1] = 0;

4.填表顺序：从左往右依次填

5.返回值：dp[n]

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) 
    {
        int n = cost.size();
        
        vector<int> dp(n + 1);
        dp[0] = 0; dp[1] = 0;
        for(int i = 2; i <= n; ++i)
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

        return dp[n];
    }
};

这是ac代码

4.解码方法

91. 解码方法

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

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法

1.状态表示：用dp[ i ]表示上到第i – 1个字母最大解码方法

2.状态转移方程：dp[i] = dp[i – 1] + dp[i – 2](要判断是否存在该情况)

3.初始化：dp[0] = 1; dp[1] = s[0] != ‘0’;

4.填表顺序：从左往右依次填

5.返回值：dp[n]

class Solution {
public:
    int numDecodings(string s) 
    {
        int n = s.size();

        vector<int> dp(n + 1);
        dp[0] = 1; 
        dp[1] = s[0] != '0';
        for(int i = 2; i <= n; ++i)
        {
            if(s[i - 1] != '0') dp[i] += dp[i - 1];
            int num = (s[i - 2] -'0') * 10 + s[i - 1] - '0';
            if(num >= 10 && num <= 26) dp[i] += dp[i - 2];
        }

        return dp[n];
    }
};

这是ac代码

新手写博客，有不对的位置希望大佬们能够指出，也谢谢大家能看到这里，让我们一起学习进步吧！