代码随想录算法训练营第三十八天| 动态规划,509. 斐波那契数,70. 爬楼梯,746. 使用最小花费爬楼梯
目录
动态规划
Dynamic programming,DP问题。某一问题包含很多重叠的子问题,每个状态都由上一个状态推导而来。问题包括:基础问题,背包问题,打家劫舍,股票问题,子序列问题,
步骤:
- 确定dp数组(dp table)以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
题目链接:509. 斐波那契数
思路
题目给出了dp五部曲中的所有信息。
代码
class Solution {
public:
int fib(int n) {
if (n <= 1)
return n;
vector<int> dp(n + 1); // 定义dp数组,dp[i]就是斐波那契数列第i个的值
dp[0] = 0;
dp[1] = 1; // 按照斐波那契数列初始化前两个数
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]; // 递推公式
}
return dp[n];
}
};
题目链接:70. 爬楼梯
思路
1阶有1中方法,2阶有两种方法,3阶则是可以从1阶或者2阶走上来,从1或者2走上来总共3种方法。递推下去,发现与斐波那契数列相同,只是该题的0阶并无含义。对求斐波那契数列的代码进行状态压缩,因为每次求值只跟前两个状态有关,因此只需要三个变量,而不是一个数组。
代码
class Solution {
public:
int climbStairs(int n) {
if (n <= 2)
return n;
int dp1 = 1; // 一阶台阶
int dp2 = 2; // 二阶台阶
int result = 0;
for (int i = 3; i <= n; i++) {
result = dp1 + dp2; // 递推公式
dp1 = dp2; // 更新
dp2 = result;
}
return result;
}
};
题目链接:746. 使用最小花费爬楼梯
思路
使用最小消费爬楼梯
1.dp[i]数组含义为到第i阶台阶所需要花费多少
2.递推公式dp[i] = min(dp[i-1]+cost[i-1], [dp[i-2]+cost[i-2])
3.根据题意和dp数组含义,可知在下标为0或1时不需要花费体力,因此dp[0]=0,dp[1]=0
4.遍历顺序,从前向后
5.如果有bug,打印dp数组debug
代码
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
vector<int> dp(cost.size() + 1); // 到第i阶的所有花费
dp[0] = 0; // 0或1阶不需要花费
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()]; // 返回最小花费
}
};
总结
①动态规划的第一天,基础知识种的五部曲很重要
②今天的题都是入门题目,较为简单,但也是看视频讲解后做的
③还是不能依赖核心代码模式,一是在ACM模式下不知道怎么下手,二是不好debug
原文地址:https://blog.csdn.net/weixin_43630246/article/details/138211606
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!