代码随想录算法【Day32】

动态规划理论基础

问题分类

动态规划基础问题

背包问题

打家劫舍

股票问题

子序列问题

每道题按照以下五部曲想清楚

DP数组的定义以及下标的含义

递推公式

DP数组如何初始化

遍历顺序

打印DP数组

Day32

509. 斐波那契数

class Solution {
public:
    int fib(int n) {
        if(n <= 1) return n;
        int dp[2];
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i <= n; i++){
            int sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }
};

五部曲

1.dp数组及下标定义：dp[0]和dp[1]表示当前遍历的数的前两个数的值，下标表示前两个数中的第一个还是第二个

2.递推公式：sum = dp[0] + dp[1];

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

4.遍历顺序：从前往后遍历

5.数组的数据应该是怎样的：0 1 1 2 3 5 8....

70. 爬楼梯

class Solution {
public:
    int climbStairs(int n) {
        int dp[2];
        dp[0] = 1;
        dp[1] = 2;
        if(n <= 1) return n;
        for(int i = 2;i < n; i++){
            int sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }
};

五部曲

1.dp数组及下标定义：dp[0]和dp[1]表示当前遍历的数的前两个数的值，下标表示前两个数中的第一个还是第二个

2.递推公式：sum = dp[0] + dp[1];

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

4.遍历顺序：从前往后遍历

5.数组的数据应该是怎样的：1 2 3 5 8

746. 使用最小花费爬楼梯

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

五部曲

1.dp数组及下标定义：dp数组的值表示到达当前阶梯所需的最小花费，下标表示当前的台阶是第几阶

2.递推公式：dp[i] = min((cost[i - 1] + dp[i - 1]), (cost[i - 2] + dp[i - 2]));

3.初始化：dp[0] = 0, dp[1] = 0; dp[2] = min(cost[0], cost[1]);

4.遍历顺序：从前往后遍历

5.数组的数据应该是怎样的：若cost.size() = 3,即存在cost[2]，此时i = 3即为登顶，返回dp[3]