理论基础
动态规划：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;
}