怎样保证网站的安全,沈阳专业的网站设计公司,北京建站开发,网站建设模板报价理论基础
动态规划#xff1a;dp#xff0c;每一个状态都是由上个状态推导出来的#xff0c;因为我是先写完三道题再看理论的#xff0c;所以有点感概#xff1b;
确定dp数组#xff08;dp table#xff09;以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举…理论基础
动态规划dp每一个状态都是由上个状态推导出来的因为我是先写完三道题再看理论的所以有点感概
确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组
509. 斐波那契数
509. 斐波那契数https://leetcode.cn/problems/fibonacci-number/
1.因为是n是动态的所以需要用malloc来分配内存因为后面会对dp赋值所以初始化的代码我注释了
2.因为求n但下标0是从开始的所以需要n1
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] ,这里n10但是a[10]是第11个斐波那契数所以需要n1
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.举例推导如下
11
21, 2
31112112
4111121112111222
这里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;
}
