代码随想录算法训练营第三八天 | 动态规划

LeetCode 509. 斐波那契数
LeetCode 70. 爬楼梯
LeetCode 746. 使用最小花费爬楼梯

动态规划基础

Dynamic Programming (DP) 如果某一问题有很多重叠子问题，使用动态规划是最有效的。

动态规划中每一个状态一定是由上一个状态推导出来的，区分于贪心，贪心是从局部直接选最优的。

• 确定dp数组（dp table）以及下标的含义
• 确定递推公式
• dp数组如何初始化
• 确定遍历顺序
• 举例推导dp数组

---

找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的！

写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。

斐波那契数

class Solution {public int fib(int n) {// dp[i] : 第i 个数的斐波那契数值// 递推公式：dp[i] = dp[i - 1] + dp[i - 2]// 初始化： dp[0] = 0;//         dp[1] = 1;// 遍历顺序: 从前到后// 举例推导 dp 数组:  0 1 1 2 3 5 8 13 21 34 55if (n <= 1) return n;int[] dp = new int[n + 1];dp[0] = 0;dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
}

也可以只维护两个元素的数组，for 循环里交换一下 :

int sum = dp[0] + dp[1];
dp[0] = dp[1];
dp[1] = sum;

递归 时间复杂度 $O(2^n)$

class Solution {public int fib(int n) {if (n <= 1) return n;return fib(n - 1) + fib(n - 2);}
}

爬楼梯

和斐波那契数列一样，dp数组每个值代表爬到第i层楼梯有 dp[i]种方法。

class Solution {public int climbStairs(int n) {// dp[i] 爬到第i层楼梯，有 dp[i]种方法// dp[i] = dp[i - 1] + dp[i - 2] // dp[1] = 1，dp[2] = 2 从i = 3 开始递推// 遍历顺序： 从前往后// 举例推导： 1 2 3 5 8if (n <= 2) return n;int[] dp = new int[3];dp[1] = 1;dp[2] = 2;for (int i = 3; i <= n; i++) {int sum = dp[1] + dp[2];dp[1] = dp[2];dp[2] = sum;}return dp[2];}
}

使用最小花费爬楼梯

class Solution {public int minCostClimbingStairs(int[] cost) {// dp[i] 到达第i台阶所花费的最小体力 // dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);// dp[0] = 0; dp[1] = 0;// 前序// 举例int[] dp = new int[cost.length + 1];dp[0] = 0;dp[1] = 0;for (int i = 2; i <= cost.length; i++) {dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}return dp[cost.length];}
}