本文主要是介绍代码随想录第三十三天(一刷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时,返回nif(n <= 1)return n;//动态开辟一个int数组,大小为n+1int *dp = (int *)malloc(sizeof(int) * (n + 1));//设置0号位为0,1号为为1dp[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,返回nif(n <= 2)return n;//初始化dp数组,数组大小为n+1int *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];
}
全篇后记:
开启全新篇章动态规划,之前有刷过但是不成体系,希望能一刷掌握思路与方法,给后面的刷题打下坚实的基础。
这篇关于代码随想录第三十三天(一刷C语言)|斐波那契数爬楼梯使用最小花费爬楼梯的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!