动态规划专练:力扣第509、70、746题

由于对动态规划DP算法 掌握得不是很好所以决定进行动态规划专项训练。动态规划五部曲①确定dp[i]含义②递推公式③dp数组如何初始化④遍历顺序⑤打印dp数组debug除了第五条在力扣上不开会员无法实现外其余四项就是做出dp类型题目的关键后续的训练中将按照这四步来进行解题。力扣第509题-斐波那契数1.本题的动态规划四部曲①dp[i]含义代表第i个斐波那契数的值。②递推公式题目中已经告诉我们了dp[i] dp[i – 1] dp[i – 2]。③初始化也在题目中dp[0] 0dp[1] 1。④遍历顺序从前向后2.本题是动态规划入门级题目可写出完整代码如下1. int fib(int n) { 2. int dp[31] {0}; 3. dp[0] 0; 4. dp[1] 1; 5. 6. if (n 2){ 7. for (int i 2; i n; i){ 8. dp[i] dp[i - 1] dp[i - 2]; 9. } 10. } 11. 12. return dp[n]; 13. }该算法时间复杂度为O(n)空间复杂度为O(n)。可以通过只保存当前遍历下标的前两个元素来将空间复杂度降为O(1)1. int fib(int n) { 2. int a 0; 3. int b 1; 4. if (n 0) return a; 5. if (n 1) return b; 6. 7. for (int i 2; i n; i){ 8. int tmp a; 9. a b; 10. b tmp; 11. } 12. 13. return b; 14. 15. }3.需要注意的是对于定义数组并赋值为0的代码1. int dp[10] {0}; // ✅ 完全正确 2. int n 5; 3. int dp[n 1]; // ✅ 定义可以 4. int dp[n 1] {0}; // ❌ 初始化 不可以固定长度的数组可以直接进行赋值为0的初始化而变长数组数组长度中含有变量只能进行定义不能进行赋值为0的初始化操作。4.本题也是递归类型题目的入门题所以用递归再写一遍1. int recursion(int n, int start, int a, int b){ 2. if (start n){ 3. return a b; 4. } 5. 6. int tmp a; 7. a b; 8. b tmp b; 9. return recursion(n, start 1, a, b); 10. } 11. 12. int fib(int n) { 13. if (n 0){ 14. return 0; 15. } 16. if (n 1){ 17. return 1; 18. } 19. 20. return recursion(n, 2, 0, 1); 21. }该算法时间复杂度为O(n)空间复杂度为O(1)。力扣第70题-爬楼梯1.本题的动态规划四部曲①dp[i]含义代表爬到第i层台阶的方法数。②递推公式爬到该层楼梯只能通过1步或者2步到达所以方法数等于前1层台阶的方法数与前2层台阶的方法数之和dp[i] dp[i – 1] dp[i – 2]。③初始化到达第1层有1种方法所以dp[1] 1而到达第二层有两种方法即1步1步到达与直接2步到达所以dp[2] dp[1] dp[0] 2初始化dp[0] 1。④遍历顺序从前向后2.基于以上思想可写出完整代码如下1. // 爬楼梯滚动变量迭代写法 —— 空间 O(1)最优解 2. int climbStairs(int n) { 3. // 定义两个滚动变量 4. // a 保存 dp[i-2] 的值前前台阶的方法数 5. int a 1; 6. // b 保存 dp[i-1] 的值前一台阶的方法数 7. int b 1; 8. 9. // 特殊情况n1直接返回 b只有1种方法 10. if (n 1) return b; 11. 12. // 从第 2 阶开始一直递推到第 n 阶 13. for (int i 2; i n; i){ 14. int tmp a; // 临时保存旧的 adp[i-2] 15. a b; // a 滚动更新变成 dp[i-1] 16. b tmp; // b 滚动更新新b 旧b 旧a → dp[i] dp[i-1]dp[i-2] 17. } 18. 19. // 循环结束后b 就是 dp[n]即答案 20. return b; 21. }该算法时间复杂度为O(n)空间复杂度为O(1)。力扣第746题-使用最小花费爬楼梯1.本题的动态规划四部曲①dp[i]含义因为从该层台阶向上跳才会收取费用所以本题dp[i]的含义为在第i层台阶向上跳所需要的最小花费。②递推公式爬到该层楼梯只能通过1步或者2步到达所以爬到本层的最小花费应该是爬到前两层的最少花费与本层花费之和dp[i] cost[i] fmin(dp[i - 1], dp[i - 2])。需要注意的是楼顶的下标为costSize而不是costSize – 1所以最后一次循环的时候需要使用的代码为dp[costSize] fmin(dp[costSize - 1], dp[costSize - 2])。③初始化dp[0] cost[0]dp[1] cost[1]相比于从0层爬到1层肯定是直接从1层出发花费更少。④遍历顺序从前向后2.基于以上思想可写出完整代码如下1. int minCostClimbingStairs(int* cost, int costSize) { 2. // 1. 定义dp数组 3. // dp[i] 到达第 i 个台阶时累计的最小花费 4. // 题目限制 costSize 1000所以开 1001 足够 5. int dp[1001] {0}; 6. 7. // 2. 初始化基准条件 8. // 可以从下标 0 或 1 开始爬所以 9. dp[0] cost[0]; // 到达第 0 阶的最小花费 cost[0] 10. dp[1] cost[1]; // 到达第 1 阶的最小花费 cost[1] 11. 12. // 3. 特殊情况只有 2 阶台阶时直接取两者最小值可以从0或1直接到顶 13. if (costSize 2) return fmin(dp[0], dp[1]); 14. 15. // 4. 递推计算从第 2 阶开始一直算到楼梯顶部第 costSize 阶 16. for (int i 2; i costSize; i){ 17. // 5. 特殊处理到达楼梯顶部i costSize 18. // 顶部不需要支付 cost所以直接取前两阶的最小值 19. if (i costSize){ 20. dp[i] fmin(dp[i - 1], dp[i - 2]); 21. } 22. // 6. 普通台阶到达第 i 阶的最小花费 cost[i] 前两阶的最小值 23. // 因为要到达 i 阶必须先付 cost[i]再从 i-1 或 i-2 阶爬上来 24. else { 25. dp[i] cost[i] fmin(dp[i - 1], dp[i - 2]); 26. } 27. } 28. 29. // 7. 最终答案到达楼梯顶部第 costSize 阶的最小花费 30. return dp[costSize]; 31. }该算法的时间复杂度和空间复杂度均为O(n)。3.实际上本题更符合题意、更清晰的做法应该是①dp的含义为到达该层台阶所需要的最小花费。②递推公式为dp[i] fmin(cost[i - 1] dp[i - 1], cost[i - 2] dp[i - 2])即要么从前1层跳上来要么从前2层跳上来最小花费为跳到前面那层的费用以及从那层起跳的费用。③初始化dp[0] 0dp[1] 0。这样做就不需要额外讨论costSize 2的边界情况。完整代码如下1. int minCostClimbingStairs(int* cost, int costSize) { 2. int dp[1001]; 3. 4. // dp[i] 到达第 i 级台阶还没往上跳时的最小花费 5. // 重点我们站在台阶上时还没支付这个台阶的费用 6. 7. dp[0] 0; // 站在第 0 级台阶不需要花费 8. dp[1] 0; // 站在第 1 级台阶不需要花费 9. 10. // 从第 2 级开始一直推到 顶部costSize 11. for (int i 2; i costSize; i){ 12. // 核心状态转移方程超级关键 13. // 到达第 i 级台阶有两种方法 14. // 1. 从 i-1 跳 1 步上来 → 花费 cost[i-1] dp[i-1] 15. // 2. 从 i-2 跳 2 步上来 → 花费 cost[i-2] dp[i-2] 16. // 取最小的那个 17. dp[i] fmin(cost[i - 1] dp[i - 1], cost[i - 2] dp[i - 2]); 18. } 19. 20. // dp[costSize] 就是到达楼梯顶部的最小花费 21. return dp[costSize]; 22. }