代码随想录算法训练营第51期第32天 | 理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯
理论基础
动态规划:dp,每一个状态都是由上个状态推导出来的,因为我是先写完三道题再看理论的,所以有点感概;
- 确定dp数组(dp table)以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
509. 斐波那契数
509. 斐波那契数https://leetcode.cn/problems/fibonacci-number/
1.因为是n是动态的,所以需要用malloc来分配内存,因为后面会对dp赋值,所以初始化的代码我注释了
2.因为求n,但下标0是从开始的,所以需要n+1
3.这里也可以用递归写,但是复杂度有点2的n次方,我就不记录了
4.我还记录了只需要用2个变量来存储结果的写法,这样就不需要用数组了
动归五部曲
1.确定dp数组以及下标的含义:dp[i]表示第i个斐波那契数
2.确定递推公式:dp[i] = dp[i-1] + dp[i-2]
3.dp数组如何初始化:dp[0] = 0, dp[1] = 1
4.确定遍历顺序:从前往后遍历
5.举例推导 a = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] ,这里n=10,但是a[10]是第11个斐波那契数,所以需要n+1
int fib(int n) {
if (n <= 1) {
return n;
}
n = n + 1;
int *dp = (int*)malloc(sizeof(int) * n);
// for (int i = 0; i < n; i++) {
// dp[i] = 0;
// }
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i < n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n-1];
}
//这里也可以用递归写,但是复杂度有点2的n次方,我就不记录了
int fib(int n) {
if (n <= 1) {
return n;
}
int fir = 0;
int sec = 1;
int tmp = 0;
for (int i = 2; i <= n ; i++) {
tmp = fir + sec;
fir = sec;
sec = tmp;
}
return sec;
}
70. 爬楼梯
70. 爬楼梯https://leetcode.cn/problems/climbing-stairs/MD,写在vscode上的东西丢了,我还得再写一次
1.这里和上一题一样,代码也差不多,除了初始化,其他代码都可以复用了。
动归五部曲
1.确定dp数组以及下标的含义:dp[i]表示第i个斐波那契数
2.确定递推公式:dp[i] = dp[i-1] + dp[i-2]
3.dp数组如何初始化:dp[1] = 1, dp[2] = 2, 这里dp[0]没有意义,但是为了统一,我还是初始化为0
4.确定遍历顺序:从前往后遍历
5.举例推导如下:
1:1
2:1, 2
3:1+1+1,2+1,1+2
4:1+1+1+1,2+1+1,1+2+1,1+1+2,2+2
这里4是第3层再加1和第2层再加2,所以4是第3层和第2层的和,所以dp[4] = dp[3] + dp[2]
int climbStairs(int n) {
if (n <= 3) {
return n;
}
n = n + 1;
int *dp = (int *)malloc(sizeof(int) * n);
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i < n; i++) {
dp[i] = dp[i-2] + dp[i-1];
}
return dp[n-1];
}
int climbStairs(int n) {
if (n <= 2) {
return n;
}
int pre = 1;
int cur = 2;
int tmp = 0;
for (int i = 3; i <= n; i++) {
tmp = pre + cur;
pre = cur;
cur = tmp;
}
return cur;
}
746. 使用最小花费爬楼梯
746. 使用最小花费爬楼梯https://leetcode.cn/problems/min-cost-climbing-stairs/1.这一题虽然说简单,但是还真不太容易想到
动归五部曲
1.确定dp数组以及下标的含义:dp[i]表示踏上该楼梯的最小花费(不包括当前楼梯的花费)
2.确定递推公式:dp[i] = min((dp[i-1] + cost[i]), (dp[i-2] + cost[i]));
3.dp数组如何初始化:dp[0] = cost[0], dp[1] = cost[1],这里就不是简单的直接加了,而且后续因为长度只有costSize,和题目要求的顶部还差一点,所以需要再求一次
4.确定遍历顺序:从前往后遍历
5.举例推导:无
#define min(a, b) (((a) < (b)) ? (a) :(b))
int minCostClimbingStairs(int* cost, int costSize) {
int *dp = (int *)malloc(sizeof(int) * costSize);
dp[0] = cost[0];
dp[1] = cost[1];
for (int i = 2; i < costSize; i++) {
dp[i] = min((dp[i-1] + cost[i]), (dp[i-2] + cost[i]));
}
int res = min(dp[costSize-2], dp[costSize-1]);
return res;
}