代码随想录算法训练营第51期第32天 | 理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

理论基础

动态规划：dp，每一个状态都是由上个状态推导出来的，因为我是先写完三道题再看理论的，所以有点感概；

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导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;
}