代码随想录算法训练营第32天 | 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯
理论基础
代码随想录
视频:从此再也不怕动态规划了,动态规划解题方法论大曝光 !| 理论基础 |力扣刷题总结| 动态规划入门_哔哩哔哩_bilibili
动规五部曲:
这里我们要用一个一维dp数组来保存递归的结果
-
确定dp数组以及下标的含义
-
确定递推公式
-
dp数组如何初始化
-
确定遍历顺序
-
打印dp数组
509. 斐波那契数
代码随想录
视频:手把手带你入门动态规划 | LeetCode:509.斐波那契数_哔哩哔哩_bilibili
class Solution {
public int fib(int n) {
if(n == 0)return 0;
if(n == 1)return 1;
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for(int i = 2;i < n + 1;i++){
dp[i] = dp[i - 2] + dp[i - 1];
}
return dp[n];
}
}
class Solution {
public int fib(int n) {
if(n == 0)return 0;
if(n == 1)return 1;
int a = 0,b = 1;
int sum = 0;
for(int i = 2;i < n + 1;i++){
sum = a + b;
a = b;
b = sum;
}
return sum;
}
}
70. 爬楼梯
代码随想录
视频:带你学透动态规划-爬楼梯(对应力扣70.爬楼梯)| 动态规划经典入门题目_哔哩哔哩_bilibili
上一级台阶有1种,上2级台阶有2种
3级台阶:1.上一级台阶(1种),再走2步 2.上2级台阶(2种),再走1步 1+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 + 1;i++){
dp[i] = dp[i - 2] + dp[i - 1];
}
return dp[n];
}
}
746. 使用最小花费爬楼梯
746. 使用最小花费爬楼梯 - 力扣(LeetCode)
代码随想录
视频讲解:动态规划开更了!| LeetCode:746. 使用最小花费爬楼梯_哔哩哔哩_bilibili
自己思路:
dp含义:dp[i]表示从i层开始,到顶层的最小花费
初始化:dp[len - 1] = cost[len - 1]; dp[len - 2] = cost[len - 2];
从最后两层开始花费当前代价就到了
递推公式:dp[i] = cost[i] + Math.min(dp[i + 1],dp[i + 2]);从i楼层起跳的代价加上i+1和i+2楼层计算的最小代价的最小值
遍历顺序:从后往前
class Solution {
public int minCostClimbingStairs(int[] cost) {
int len = cost.length;
int[] dp = new int[len];
dp[len - 1] = cost[len - 1];
dp[len - 2] = cost[len - 2];
for(int i = len - 3;i >= 0;i--){
dp[i] = cost[i] + Math.min(dp[i + 1],dp[i + 2]);
}
return Math.min(dp[0],dp[1]);
}
}
随想录的
dp含义:到i层的代价
递推公式:dp[i] = Math.min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]);
初始化:dp[0] = 0; dp[1] = 0;
遍历顺序:从前往后
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 + 1;i++){
dp[i] = Math.min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]);
}
return dp[len];
}
}