算法训练day41 509.70.746

动态规划理论基础

什么是动态规划
- 每一状态由上一状态推导而来
解题步骤
1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组
debug:
- 打印dp数组，和预期比较

509. 斐波那契数

题目

509. 斐波那契数 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

class Solution
{
public:
    int fib(int n)
    {
        if (n <= 1)
            return n;
        int dp[3] = {0, 1, 0}; //dp中第3位用来记录前两位的和；
        for (int i = 2; i <= n; i++)
        {
            dp[2] = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = dp[2];
        }
        return dp[1];
    }
};

70. 爬楼梯

题目

https://leetcode.cn/problems/climbing-stairs/

题解

代码随想录 (programmercarl.com)

第n阶台阶可以通过前一阶迈一步，也可以通过前前一阶迈两阶所以dp[n]=dp[n-1]+[n-2];

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return n; 
        vector<int> dp(n + 1);
        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. 使用最小花费爬楼梯

题目

746. 使用最小花费爬楼梯 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

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