题目:
- 斐波那契数
- 爬楼梯
- 使用最小花费爬楼梯
动态规划简称DP,如果某一问题有很多重叠子问题,使用动态规划是最有效的。所以动态规划中每一个状态一定是由上一个状态推导出来的。动态规划有五个步骤:
- 确定dp数组以及下标的含义;
- 确定递归公式;
- dp数组如何初始化;
- 确定遍历顺序;
- 举例推导dp数组;
学习内容:
509. 斐波那契数
class Solution {public int fib(int n) {if (n <= 1) return n;// 1. 确定dp数组int[] dp = new int[n + 1];// 2. dp数组的初始化dp[0] = 0;dp[1] = 1;// 3. 确定遍历顺序for (int i = 2; i <= n; i++) {// 4. 举例推导dp数组dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
}
70. 爬楼梯
这道题的重点就是找到dp数组的含义,dp[i]的含义是,爬到第i层楼梯,有dp[i]种方法。 其次,我们需要找到递归公式。
楼梯数 | 方法 |
---|---|
一层 | 1 |
二层 | 2 |
三层 | 1+2 |
从表中可以发现,如果楼梯数为3,那么一层走2步可以完成任务,二层走1步也可以完成任务。所以走到第三层的方法数量就是一层的方法加二层的方法,递归公式就可以抽象为:dp[i] = dp[i - 1] + dp[i - 2];
class Solution {public int climbStairs(int n) {if (n <= 1) return n;int[] dp = new int[n + 1];dp[1] = 1;dp[2] = 2;for (int i = 3; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
}
这道题其实本质上就是斐波那契数列,因为当前数都是前两个数的和。
746. 使用最小花费爬楼梯
dp[i]表示到达第i个阶梯的所花费的最小费用,当前最小费用实际上只和i - 1和i - 2有关系,递归公式:Min(d[i - 1] + cost[i - 1], d[i - 2] + cost[i - 2])
class Solution {public int minCostClimbingStairs(int[] cost) {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];}
}
学习时间:
2024.4.23