代码随想录第三十三天(一刷&&C语言)|斐波那契数&&爬楼梯&&使用最小花费爬楼梯
创作目的:为了方便自己后续复习重点,以及养成写博客的习惯。
动态规划步骤:
- 确定dp数组以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
一、斐波那契数
思路:参考carl文档
1、dp[i]的定义为:第i个数的斐波那契数值是dp[i]。
2、递推公式为:?dp[i] = dp[i - 1] + dp[i - 2]。
3、dp数组初始化:dp[0] = 0,dp[1] = 1。
4、从递归公式可以看出,dp[i]是依赖于 dp[i - 1] 和 dp[i - 2],遍历的顺序为从前到后遍历。
5、自己模拟推到dp数组,debug的时候添加打印。
ledcode题目:https://leetcode.cn/problems/fibonacci-number/
AC代码:
int fib(int n){
//当n <= 1时,返回n
if(n <= 1)
return n;
//动态开辟一个int数组,大小为n+1
int *dp = (int *)malloc(sizeof(int) * (n + 1));
//设置0号位为0,1号为为1
dp[0] = 0;
dp[1] = 1;
//从前向后遍历数组(i=2; i <= n; ++i),下标为n时的元素为dp[i-1] + dp[i-2]
int i;
for(i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
二、爬楼梯
思路:参考carl文档
1、dp[i]的定义为: 爬到第i层楼梯,有dp[i]种方法。
2、确定递推公式:dp[i] = dp[i - 1] + dp[i - 2] 。
3、dp数组初始化:不初始化dp[0],只初始化dp[1] = 1,dp[2] = 2,从i = 3开始递推。
4、从递推公式可知遍历顺序是从前向后遍历。
5、举例当n为4的时候,dp[4] = 5。
lecode题目:https://leetcode.cn/problems/climbing-stairs/description/
AC代码:
int climbStairs(int n){
//若n<=2,返回n
if(n <= 2)
return n;
//初始化dp数组,数组大小为n+1
int *dp = (int *)malloc(sizeof(int) * (n + 1));
dp[0] = 0, dp[1] = 1, dp[2] = 2;
//从前向后遍历数组,dp[i] = dp[i-1] + dp[i-2]
int i;
for(i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
//返回dp[n]
return dp[n];
}
三、使用最小花费爬楼梯
思路:参考carl文档
1、dp[i]的定义为:到达第i台阶所花费的最少体力为dp[i]。
2、确定递推公式为:dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])。
3、dp数组初始化:dp[0] = 0,dp[1] = 0。
4、dp[i]由dp[i-1]dp[i-2]推出,故从前到后遍历cost数组。
5、举例推导dp数组(模拟一组cost)
ledcode题目:https://leetcode.cn/problems/min-cost-climbing-stairs/description/
AC代码:
#include <math.h>
int minCostClimbingStairs(int *cost, int costSize) {
int dp[costSize + 1];
dp[0] = dp[1] = 0;
for (int i = 2; i <= costSize; i++) {
dp[i] = fmin(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
}
return dp[costSize];
}
全篇后记:
? ? ? ? 开启全新篇章动态规划,之前有刷过但是不成体系,希望能一刷掌握思路与方法,给后面的刷题打下坚实的基础。
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!