【刷题27】动态规划—斐波那契数列模型

一、第N个泰波那契数

题目：

思路：

• 状态方程：dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
• 因为第一个数是从0开始，所以数组存放数据时要多开一个
• n=0 返回0，n=1或2 返回1
• dp[0/1/2]要初始化
• 最后返回dp[n]，即最后一个元素

代码：

class Solution {
public:
    int tribonacci(int n) {
        if(n == 0) return 0;
        if(n == 1 || 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];
    }
};

二、三步问题

题目：

思路：

• 数据范围较大，要对结果取模
• dp多开一个
• 状态方程：dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
• dp[1/2/3]初始化
• 返回dp[n]

代码：

class Solution {
public:
    int waysToStep(int n) {
        int mod = 1e9+7;
        if(n == 1 || n == 2) return n;
        if(n == 3) return 4;
        vector<int> dp(n+1);
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for(int i=4; i<=n;i++)
        {
            dp[i] = ((dp[i-1]+dp[i-2])%mod+dp[i-3])%mod;
        }
        return dp[n];
    }
};

三、最小花费爬楼梯

题目：

思路：
因为是每次向上爬一个或两个台阶，所以可以理解为本次花费为前一个台阶的花费与前两个花费的较小值

状态转移方程： dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
初始化：i从2开始，因为要保证i-1和i-2不越界。dp[0]和dp[1] 初始化为0，cost数组才是表示每条台阶有费用的

注意：楼顶——状态表示数组的最后一个位置不是cost数组的最后一个位置，要多加一个

返回值是楼顶位置，此时就是花费最小

代码：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n+1);
        dp[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];
    }
};