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

代码随想录Day 32|leetcode题目：501.斐波那契数、70.爬楼梯、746.使用最小花费爬楼梯

article 2024/11/21 1:22:46

提示：DDU，供自己复习使用。欢迎大家前来讨论~

文章目录

动态规划理论基础
一、理论基础
1.1 什么是动态规划
1.2 动态规划的解题步骤
1.3 动态规划应该如何debug

二、题目
题目一： 509. 斐波那契数
解题思路：
动态规划
递归解法

题目二：70. 爬楼梯
解题思路：

题目三： 746. 使用最小花费爬楼梯
解题思路

总结

动态规划理论基础

开始动态规划算法

一、理论基础

1.1 什么是动态规划

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的

1.2 动态规划的解题步骤

对于动态规划问题，将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

1.3 动态规划应该如何debug

找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的！

做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。

二、题目

题目一： 509. 斐波那契数

509. 斐波那契数

解题思路：

动态规划

动规五部曲：

这里我们要用一个一维dp数组来保存递归的结果

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

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

确定递推公式
dp数组如何初始化

int n = 4;
for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
        cout << i << " " << j << endl;
    }
}

确定遍历顺序

从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的

举例推导dp数组

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

0 1 1 2 3 5 8 13 21 34 55

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

以上我们用动规的方法分析完了，C++代码如下

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)

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

代码如下：

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)

递归解法

递归函数的返回值以及参数

在这里要定义两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合。

class Solution {
public:
    int fib(int N) {
        if (N < 2) return N;
        return fib(N - 1) + fib(N - 2);
    }
};

时间复杂度：O(2^n)
空间复杂度：O(n)，算上了编程语言中实现递归的系统栈所占空间

题目二：70. 爬楼梯

70. 爬楼梯

解题思路：

本题如果没有接触过的话，会感觉比较难，多举几个例子，就可以发现其规律。

爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。

那么第一层楼梯再跨两步就到第三层，第二层楼梯再跨一步就到第三层。

所以到第三层楼梯的状态可以由第二层楼梯和到第一层楼梯状态推导出来，那么就可以想到动态规划了。

动规五部曲：

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

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

确定递推公式

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

dp数组如何初始化
确定遍历顺序

从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍历顺序一定是从前向后遍历的

举例推导dp数组

举例当n为5的时候，dp table（dp数组）应该是这样的

// 版本一
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)$

优化一下空间复杂度，代码如下：

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

时间复杂度： $O (n)$
空间复杂度： $O (1)$

题目三： 746. 使用最小花费爬楼梯

746. 使用最小花费爬楼梯

解题思路

定义dp数组：
- dp[i] 表示到达第 i 个台阶所需的最少体力。
建立递推关系：
- 每个台阶 i 可以从台阶 i-1 或 i-2 跳上来。
- dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])。
初始化dp数组：
- dp[0] 和 dp[1] 都初始化为 0，因为到达第一个台阶不需要体力。
确定遍历顺序：
- 从第一个台阶开始，逐个计算每个台阶的 dp[i] 值。
举例说明：
- 通过一个具体的例子（如 cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]），展示 dp 数组如何逐步构建。
具体的结果如下图所示：

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)

还可以优化空间复杂度，因为dp[i]就是由前两位推出来的，那么也不用dp数组了，C++代码如下：

// 版本二
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int dp0 = 0;
        int dp1 = 0;
        for (int i = 2; i <= cost.size(); i++) {
            int dpi = min(dp1 + cost[i - 1], dp0 + cost[i - 2]);
            dp0 = dp1; // 记录一下前两位
            dp1 = dpi;
        }
        return dp1;
    }
};