day38打卡-Toy模板网

这篇具有很好参考价值的文章主要介绍了day38打卡。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

day38打卡

509. 斐波那契数

状态表示：

第i个数的斐波那契数是dp[i]

状态转移方程

见题目：dp[i] = dp[i-1] + dp[i-2]

初始化

见题目，dp[0] = 0，dp[1] = 1，本题用两个变量代替即可。

填表顺序

从左到右

返回值

dp[i]

class Solution {
public:
    int fib(int n) {
        if(n <= 1) return n;
        int a = 0, b = 1;
        int ret = 0;
        for(int i = 2; i <= n; i++)
        {
            ret = a + b;
            a = b;
            b = ret;
        }
        return ret;
    }
};

70. 爬楼梯

状态表示：

爬到第i层，一共用dp[i]种方法

状态转移方程

到达第i层，前一级可以是i-1，也可以是i-2(题目提到可以走1或者2步)，参照之前的状态表示

所以dp[i] = dp[i-1] + dp[i-2]

初始化

dp[1] = 1，dp[2] = 2

填表顺序

从左到右

返回值

dp[n]

class Solution {
public:
    int climbStairs(int n) {
        if(n <= 1) return n;
        //创建dp表
        vector<int> dp(n+1, 0);
        //初始化
        dp[1] = 1, dp[2] = 2;
        //填表
        for(int i = 3; i <= n; i++)
        {
            dp[i] = dp[i-1] + dp[i-2];
        }
        //返回值
        return dp[n];
    }
};

746. 使用最小花费爬楼梯

状态表示：

爬到第i层最少需要花dp[i]的钱

状态转移方程

第i层的前一级是i-1层，或者是i-2层，选择一个花费少的即可(即为之前的花费+当前层的花费)

dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])

初始化

无特殊处理

填表顺序

从左到右

返回值

dp[n]

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        //创建dp数组
        int n = cost.size();
        vector<int> dp(n+1);
        //初始化
        //填表
        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];
    }
};