前言
思路及算法思维,指路 代码随想录。
题目来自 LeetCode。
day 38,愉快的周五,来啦~
题目详情
[509] 斐波那契数
题目描述
解题思路
前提:斐波那契数
思路:递归 or 动态规划。
重点: 动态规划数组的定义
代码实现
C语言
递归
int fib(int n){
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
return fib(n - 1) + fib(n - 2);
}
动态规划
// 第i个数的斐波那契数值是dp[i]
int fib(int n){
if (n <= 1) {
return n;
}
int dp[n + 1];
// 初始化动态规划数组
dp[0] = 0;
dp[1] = 1;
// 遍历
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 2] + dp[i - 1];
}
return dp[n];
}
[70] 爬楼梯
题目描述
解题思路
前提:每次你可以爬 1 或 2 个台阶
思路:动态规划,dp[i]代表第i阶的方法数, dp[i] = dp[i-1] + dp[i-2]
重点:动态规划数组的定义及初始化
代码实现
C语言
动态规划
// dp[i]代表第i阶的方法数, dp[i] = dp[i-1] + dp[i-2]
int climbStairs(int n) {
if (n <= 2) {
return n;
}
// dp数组初始化
int dp[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
[746] 使用最小花费爬楼梯
题目描述
解题思路
前提:可以从0或1开始爬楼梯,每次你可以爬 1 或 2 个台阶,最后一个台阶到楼顶依旧需要走一步
思路:动态规划,到达第i个楼梯的最低费用, dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
重点:动态规划数组的定义及初始化
代码实现
C语言
动态规划
// dp[i]: 到达第i个楼梯的最低费用, dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
int min(int p1, int p2) {
return p1 < p2 ? p1 : p2;
}
int minCostClimbingStairs(int* cost, int costSize) {
int dp[costSize + 1];
// dp数组初始化
dp[0] = 0;
dp[1] = 0;
if (costSize <= 1) {
return 0;
}
// 最后一个台阶到楼顶依旧需要走一步
for (int i = 2; i <= costSize; i++) {
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[costSize];
}
今日收获
- 动态规划五步曲:确定dp数组(dp table)以及下标的含义;确定递推公式;dp数组如何初始化;确定遍历顺序;举例推导dp数组。