侧边栏壁纸
博主头像
thinkTV博主等级

喜爱动漫的二刺螈一枚,摩托车云爱好者(快要有车了)。 懂一点技术的在读生物医学工程研究生( •̀ ω •́ )✧,多多指教。

  • 累计撰写 127 篇文章
  • 累计创建 17 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

代码随想录算法训练营第三十八天 | 动态规划理论基础;斐波那契数;爬楼梯;使用最小花费爬楼梯

thinkTV
2023-05-27 / 0 评论 / 0 点赞 / 79 阅读 / 1,369 字 / 正在检测是否收录...

1. 动态规划理论基础

代码随想录:原文

1.1 什么是动态规划

  • 动态规划,英文:Dynamic Programming,简称DP,如果某一问题有很多重叠子问题,使用动态规划是最有效的
  • 动规是由前一个状态推导出来的,而贪心是局部直接选最优的

1.2 动态规划的解题步骤

对于动态规划问题,我将拆解为如下五步曲

  1. 确定dp数组(dp table)以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组
  • 要先确定递推公式,然后在考虑初始化,一些情况是递推公式决定了dp数组要如何初始化

1.3 动态规划应该如何debug

  • 找问题的最好方式就是把dp数组打印出来,看看究竟是不是按照自己思路推导的
  • 做动规的题目,写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍,心中有数,确定最后推出的是想要的结果

debug三问:

  • 这道题目我举例推导状态转移公式了么?
  • 我打印dp数组的日志了么?
  • 打印出来了dp数组和我想的一样么?

2. 斐波那契数

代码随想录:原文

力扣题目:509. 斐波那契数

2.1 思路

动态规划

动规五部曲:

  1. 确定dp数组以及下标的含义
  • dp[i]的定义为:第i个数的斐波那契数值是dp[i]
  1. 确定递推公式

状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];

  1. dp数组如何初始化
dp[0] = 0;
dp[1] = 1;
  1. 确定遍历顺序
  • 从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,dp[i]是依赖 dp[i - 1] 和 dp[i - 2],那么遍历的顺序一定是从前到后遍历的
  1. 举例推导dp数组
  • 当N为10的时候,dp数组应该是数列:0 1 1 2 3 5 8 13 21 34 55
  • 如果代码写出来,发现结果不对,就把dp数组打印出来看看和我们推导的数列是不是一致的。

2.2 代码实现

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

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

PS:我们只需要维护两个数值就可以了,不需要记录整个序列

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];
    }
};

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

3. 爬楼梯

代码随想录:原文

力扣题目:70. 爬楼梯

3.1 思路

  • 第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来

动规五部曲:

  1. 确定dp数组以及下标的含义
  • dp[i]: 爬到第i层楼梯,有dp[i]种方法
  1. 确定递推公式
  • dp[i] = dp[i - 1] + dp[i - 2]
  1. dp数组如何初始化
  • 不考虑dp[0]如何初始化
  • 只初始化dp[1] = 1,dp[2] = 2,然后从i = 3开始递推
  1. 确定遍历顺序
  • 遍历顺序一定是从前向后遍历的
  1. 举例推导dp数组

图片-1

3.2 代码实现

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return n; // 因为下面直接对dp[2]操作了,防止空指针
        vector<int> dp(n + 1);
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) { // 注意i是从3开始的
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};
  • 时间复杂度:O(n)O(n)
  • 空间复杂度:O(n)O(n)

4. 使用最小花费爬楼梯

代码随想录:原文

力扣题目:746. 使用最小花费爬楼梯

4.1 思路

动规五部曲:

  1. 确定dp数组以及下标的含义
  • dp[i]的定义:到达第i台阶所花费的最少体力为dp[i]
  1. 确定递推公式
  • 可以有两个途径得到dp[i],一个是dp[i-1] 一个是dp[i-2]
  • dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。
  • dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。
  • dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
  1. dp数组如何初始化
  • 题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
  • 所以初始化 dp[0] = 0,dp[1] = 0;
  1. 确定遍历顺序
  • 从前到后遍历cost数组
  1. 举例推导dp数组

图片-2

4.2 代码实现

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()];
    }
};

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

5. 总结

  • 对于dp数组的定义一定要清晰
  • 动规五部曲

学习时间:140min

0

评论区