前置知识
解题思路
动态规划（DP，Dynamic Programming）。
其解题思路对比贪心算法的“直接选局部最优然后推导出全局最优”；倾向于“由之前的结果推导得到后续的结果”。
很多时候二者具有相似性，不必死扣概念。
解题步骤
动态规划题目的核心是dp数组的概念和构建(递推公式);
所以具体的解题步骤可以分为以下几步:
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
动态规划的debug
每走一步都将dp数组打印出来, 检查是否和自己推导和计划的一致.
当出现bug的时候, 思考:
- 这道题目我举例推导状态转移公式了么？
- 我打印dp数组的日志了么？
- 打印出来了dp数组和我想的一样么？
参考文章：动态规划理论基础
509. 斐波那契数
题目描述
LeetCode链接：https://leetcode.cn/problems/fibonacci-number/description/
解题思路
因为是简单题, 所以直接给出了递推公式, 我们只需要先构建dp数组的前两项, 然后依次向后传递推导即可.
代码
使用dp数组
class Solution {
public:
int fib(int n) {
vector<int> fei;
fei.push_back(0);
fei.push_back(1);
for(int i=2; i<=n; ++i){
fei.push_back(fei[i-1] + fei[i-2]);
}
return fei[n];
}
};
优化空间复杂度: 不用数组, 只用两个变量记录即可
class Solution {
public:
int fib(int n) {
if(n==0) return 0;
else if(n==1) return 1;
int first=0, second=1;
for(int i=2; i<=n; ++i){
int tmp = first + second;
first = second;
second = tmp;
}
return second;
}
};
70. 爬楼梯
题目描述
LeetCode链接：https://leetcode.cn/problems/climbing-stairs/description/
解题思路
本质上和前一题的斐波那契数列是一样的.
发现第i阶的可能性, 是i-1阶和i-2阶的和
可以理解为: 从i-1阶和i-2阶都可以直接到达i阶, 所以dp[i]=dp[i-1]+dp[i-2]
代码
使用dp数组
class Solution {
public:
int climbStairs(int n) {
vector<int> dp;
dp.push_back(1);
dp.push_back(1);
for(int i=2; i<=n; i++){
dp.push_back(dp[i-1] + dp[i-2]);
}
return dp[n];
}
};
优化空间复杂度: 不用数组, 只用两个变量记录即可
class Solution {
public:
int climbStairs(int n) {
if(n==0 || n==1) return 1;
int first=1, second=1;
for(int i=2; i<=n; i++){
int tmp = first+second;
first = second;
second = tmp;
}
return second;
}
};
746. 使用最小花费爬楼梯
题目描述
LeetCode链接：https://leetcode.cn/problems/min-cost-climbing-stairs/description/
解题思路
思路: 动态规划dp[i] 表示从i处起跳的话, 需要支付的费用
那么就有: dp[i] = min(dp[i-1], dp[i-2]) + cost[i];
代码
使用dp数组
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n=cost.size();
vector<int> dp(n);
dp[0] = cost[0];
dp[1] = cost[1];
for(int i=2; i<n; ++i){
dp[i] = min(dp[i-1], dp[i-2]) + cost[i];
}
return min(dp[n-1], dp[n-2]);
}
};
优化空间复杂度
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n=cost.size();
int first = cost[0];
int second = cost[1];
for(int i=2; i<n; ++i){
int tmp = min(first, second) + cost[i];
first = second;
second = tmp;
}
return min(first, second);
}
};
另一种动态规划思路
用另一种思路来构建dp数组:
刚才认为"dp[i]是从i处起跳需要支付的代价", 现在认为"dp[i]是到达i需要支付的代价"
递推公式也就变为: dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
所以最开始的dp[0]和dp[1]初始化为0, dp的长度也设置为cost.size()+1, 一路推导到dp[cost.size()], 直接return即可文章来源：https://www.toymoban.com/news/detail-700449.html
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()];
}
};
总结
本文参考：
斐波那契数
爬楼梯
使用最小花费爬楼梯文章来源地址https://www.toymoban.com/news/detail-700449.html
到了这里，关于LeetCode刷题笔记【29】：动态规划专题-1（斐波那契数、爬楼梯、使用最小花费爬楼梯）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
