当前位置：首页 > article >正文

代码随想录刷题day32丨动态规划理论基础，509. 斐波那契数， 70. 爬楼梯， 746. 使用最小花费爬楼梯

article 2024/11/15 18:32:16

代码随想录刷题day32丨动态规划理论基础，509. 斐波那契数， 70. 爬楼梯， 746. 使用最小花费爬楼梯

1.动态规划理论基础

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。
动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的
动态规划的解题步骤（动规五步曲）
1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组
为什么要先确定递推公式，然后在考虑初始化呢？
- 因为一些情况是递推公式决定了dp数组要如何初始化！
代码出错找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的！
做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。

然后再写代码，如果代码没通过就打印dp数组，看看是不是和自己预先推导的哪里不一样。

如果打印出来和自己预先模拟推导是一样的，那么就是自己的递归公式、初始化或者遍历顺序有问题了。

如果和自己预先模拟推导的不一样，那么就是代码实现细节有问题。

2.题目

2.1斐波那契数

题目链接：509. 斐波那契数 - 力扣（LeetCode）

在这里插入图片描述

视频讲解：手把手带你入门动态规划 | LeetCode：509.斐波那契数_哔哩哔哩_bilibili
文档讲解：https://programmercarl.com/0509.%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0.html

解题思路：动态规划

确定dp数组以及下标的含义

dp[i]的定义为：第i个数的斐波那契数值是dp[i]

确定递推公式
```
dp[i] = dp[i - 1] + dp[i - 2]
```
dp数组如何初始化
```
dp[0] = 0;
dp[1] = 1;
```
确定遍历顺序
```
从前到后遍历
```

举例推导dp数组

按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：

0 1 1 2 3 5 8 13 21 34 55

如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。

代码：

//dp解法
//时间复杂度：O(n)
//空间复杂度：O(n)
class Solution {
    public int fib(int n) {
        if(n <= 1){
            return n;
        }
        int[] dp = new int[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];
    }
}

//压缩版dp,只需要维护两个数值就可以了，不需要记录整个序列
//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
    public int fib(int n) {
        if(n <= 1){
            return n;
        }
        int a = 0;
        int b = 1;
        int c = 0;
        for(int i = 2;i <= n;i++){
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}

//递归解法
//时间复杂度：O(2^n)
//空间复杂度：O(n)，算上了编程语言中实现递归的系统栈所占空间
class Solution {
    public int fib(int n) {     
        if(n <= 1){
            return n;
        }
        return fib(n - 1) + fib(n - 2);
    }
}

总结：
- 动规五部曲方法很重要！

2.2爬楼梯

题目链接：70. 爬楼梯 - 力扣（LeetCode）
视频讲解：带你学透动态规划-爬楼梯（对应力扣70.爬楼梯）| 动态规划经典入门题目_哔哩哔哩_bilibili
文档讲解：https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF.html

解题思路：动态规划

确定dp数组以及下标的含义

dp[i]： 爬到第i层楼梯，有dp[i]种方法

确定递推公式
```
dp[i] = dp[i - 1] + dp[i - 2] 
```
dp数组如何初始化
```
dp[1] = 1，dp[2] = 2
```
确定遍历顺序
```
从前向后遍历
```

举例推导dp数组

举例当n为5的时候，dp数组应该是：

在这里插入图片描述

代码：

class Solution {
    public int climbStairs(int n) {
        if(n == 1){
            return 1;
        }
        int[] dp = new int[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];
    }
}

为什么需要特殊处理 `n = 1`？

如果 n = 1，代码只需要直接返回 1，因为到达第 1 阶只有一种方法：一步爬到。
而当 n = 1 时，你不应该初始化 dp[2] = 2;，因为数组中只有 dp[0] 和 dp[1]，dp[2] 并不存在，试图访问它会引发数组越界。

总结：
- 题目中要求的每次可以爬1或者2个台阶，也就是说，最终到达n阶台阶有两种方式，一个是爬1阶台阶到达（对应的是从n-1阶台阶开始），那么另一个就是爬2阶台阶到达（对应的是从n-2阶台阶开始爬），而爬n-1阶和n-2阶台阶的方法有dp【n-1】，dp【n-2】个。所以最终爬n阶台阶的方法种类就是dp【n-1】+dp【n-2】。其实也对应了卡哥所说的从n-1和n-2阶爬上去，探究的是几种走法，而不是几步。
- 没有讨论dp[0]应该是什么，因为dp[0]在本题没有意义！

2.3使用最小花费爬楼梯

题目链接：746. 使用最小花费爬楼梯 - 力扣（LeetCode）
视频讲解：动态规划开更了！| LeetCode：746. 使用最小花费爬楼梯_哔哩哔哩_bilibili
文档讲解：https://programmercarl.com/0746.%E4%BD%BF%E7%94%A8%E6%9C%80%E5%B0%8F%E8%8A%B1%E8%B4%B9%E7%88%AC%E6%A5%BC%E6%A2%AF.html

解题思路：动态规划

图示

确定dp数组以及下标的含义

dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]

确定递推公式

可以有两个途径得到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 - 1]跳还是从dp[i - 2]跳呢？

一定是选最小的，所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

dp数组如何初始化

dp[0] = 0;//到达 第 0 个台阶是不花费的，但从 第0 个台阶 往上跳的话，需要花费 cost[0]。
dp[1] = 0;//到达 第 1 个台阶是不花费的，但从 第1 个台阶 往上跳的话，需要花费 cost[1]。

确定遍历顺序
```
从前到后遍历
```

举例推导dp数组

拿示例2：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ，来模拟一下dp数组的状态变化，如下：

在这里插入图片描述

代码：

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length + 1];
        // 从下标为 0 或下标为 1 的台阶开始，因此支付费用为0
        dp[0] = 0;
        dp[1] = 0;
        // 计算到达每一层台阶的最小费用
        for(int i = 2;i <= cost.length;i++){
            dp[i] = Math.min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.length];
    }
}