动态规划中每一个状态一定是由上一个状态推导出来的,这一点就区分于贪心,贪心没有状态推导,而是从局部直接选最优的。
第一题:509. Fibonacci Number
class Solution { public int fib(int n) { if (n < 2) return n; int a = 0, b = 1, c = 0; for (int i = 1; i < n; i++) { c = a + b; a = b; b = c; } return c; } }
//非压缩状态的版本 class Solution { public int fib(int n) { if (n <= 1) return n; int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = 1; for (int index = 2; index <= n; index++){ dp[index] = dp[index - 1] + dp[index - 2]; } return dp[n]; } }
第二题:70. Climbing Stairs
这题和第一题的斐波那契数是差不多的。
// 常规方式 public int climbStairs(int n) { int[] dp = new int[n + 1]; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; }
// 用变量记录代替数组 class Solution { public int climbStairs(int n) { if(n <= 2) return n; int a = 1, b = 2, sum = 0; for(int i = 3; i <= n; i++){ sum = a + b; // f(i - 1) + f(i - 2) a = b; // 记录f(i - 1),即下一轮的f(i - 2) b = sum; // 记录f(i),即下一轮的f(i - 1) } return b; } }
第三题: 746. Min Cost Climbing Stairs
// 方式一:第一步不支付费用 class Solution { public int minCostClimbingStairs(int[] cost) { int len = cost.length; int[] dp = new int[len + 1]; // 从下标为 0 或下标为 1 的台阶开始,因此支付费用为0 dp[0] = 0; dp[1] = 0; // 计算到达每一层台阶的最小费用 for (int i = 2; i <= len; i++) { dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); } return dp[len]; } }
// 方式二:第一步支付费用 class Solution { public int minCostClimbingStairs(int[] cost) { int[] dp = new int[cost.length]; dp[0] = cost[0]; dp[1] = cost[1]; for (int i = 2; i < cost.length; i++) { dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i]; } //最后一步,如果是由倒数第二步爬,则最后一步的体力花费可以不用算 return Math.min(dp[cost.length - 1], dp[cost.length - 2]); } }
// 状态压缩,使用三个变量来代替数组 class Solution { public int minCostClimbingStairs(int[] cost) { // 以下三个变量分别表示前两个台阶的最少费用、前一个的、当前的。 int beforeTwoCost = 0, beforeOneCost = 0, currentCost = 0; // 前两个台阶不需要费用就能上到,因此从下标2开始;因为最后一个台阶需要跨越,所以需要遍历到cost.length for (int i = 2; i <= cost.length; i ++) { // 此处遍历的是cost[i - 1],不会越界 currentCost = Math.min(beforeOneCost + cost[i - 1], beforeTwoCost + cost[i - 2]); beforeTwoCost = beforeOneCost; beforeOneCost = currentCost; } return currentCost; } }