LeetCode算法训练-动态规划
欢迎关注个人公众号:爱喝可可牛奶
LeetCode算法训练-动态规划
理论知识
动态规划当前状态是由前一个状态推导出来的,而贪心没有状态的转移
动态规划需要借助dp数组,可能是一维也可能是二维的
- 首先要明确dp数组是用来干什么的,下标对应什么
- 状态如何转移 ? 也就是理清递推公式
- dp数组如何初始化
- 如何遍历
- 举个栗子模拟推导一遍
LeetCode 509. 斐波那契数
分析
F(n) = F(n - 1) + F(n - 2),其中 n > 1
代码
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];
}
}
LeetCode 70. 爬楼梯
分析
错误 没有理清递推函数
class Solution {
public int climbStairs(int 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]+2;
}
return dp[n];
}
}
dp[i]表示到当前楼梯有多少种跳法,从这里可以往后跳一步或者两步,这样就建立了前后阶梯的关系,但是不能跳2个一步
当前阶梯跳数能由前一个阶梯跳一步或前两个阶梯跳两步得到
代码
class Solution {
public int climbStairs(int n) {
if(n == 1){
return 1;
}
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];
}
}
LeetCode 746. 使用最小花费爬楼梯
整数数组 cost ,cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦支付此费用,即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
分析
根据测试用例能够得出台阶顶部在哪里,cost[i] :从下标i-1爬一步,从i-2爬两步到台阶顶部
dp[i]表示爬到第i个台阶的最小花费,
状态转移:dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
代码
class Solution {
public int minCostClimbingStairs(int[] cost) {
int len = cost.length;
int[] dp = new int[len+1];
// 初始化
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];
}
}
总结
- 搞清楚dp数组含义以及对应下标反映了什么状态
- 弄清楚转移公式
- 初始化
- 确定遍历顺序(这个和转移公式紧密相关)
- 模拟一下
热门相关:帝少的专属:小甜心,太缠人 姐妹们的丑闻 时间都知道 别那么骄傲 寂静王冠