目录
题目1: 509. 斐波那契数
- 题目链接:509. 斐波那契数
1- 思路
动规五部曲
- 1.确定dp数组(dp table)以及下标的含义
- 2.确定递推公式
- 3.dp数组如何初始化
- 4.确定遍历顺序
- 5.举例推导dp数组
2- 题解
⭐ 斐波那契数——题解思路
class Solution {
public int fib(int n) {
if (n <= 1) return n;
// 1.确定 dp 数组以及下标含义
// dp 数组大小为 n 下标代表对应位置的斐波那契数列值
int[] dp = new int [n+1];
// 2. 确定递推函数 F(n) = F(n-1) + F(n-2)
// 3. dp 数组初始化,
dp[0] = 0;
dp[1] = 1;
// 4. 确定遍历顺序 遍历 dp 数组
for(int i = 2;i<=n;i++){
dp[i] = dp[i-2] + dp[i-1];
}
// 返回结果
return dp[n];
}
}
题目2: 70. 爬楼梯
- 题目链接:70. 爬楼梯
1- 思路
爬楼梯每次只能走 1 或者 2 步,因此当前楼梯到达的方式取决于 dp[i-1]
和 dp[i-2]
的总和
- 1. 定义 dp 数组,确定下标含义:
- dp 数组代表走到当前位置的方式
- 2. 确定递推函数
- dp[i] = dp[i-1] + dp[i-2]
- 3. 初始化dp数组
- dp[0] = 1;
- dp[1] = 1;
- 4. 确定遍历顺序
- 从 i = 2 开始遍历,遍历到 n-1
2- 题解
⭐ 爬楼梯——题解思路
class Solution {
public int climbStairs(int n) {
if(n<=1){
return 1;
}
// 1. 定义dp数组
int[] dp = new int[n];
// 2. 递推公式 dp[i] = dp[i-1] + dp[i-2];
// 初始化
dp[0] = 1;
dp[1] = 2;
for(int i = 2 ; i < n;i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n-1];
}
}
题目3:746. 使用最小花费爬楼梯
- 题目链接:746. 使用最小花费爬楼梯
1- 思路
爬楼梯每次只能走 1 或者 2
- 1. 定义 dp 数组,确定下标含义:
- dp 数组代表走到当前位置的花费,其中 dp 数组大小为
cost.length+1
- dp 数组代表走到当前位置的花费,其中 dp 数组大小为
- 2. 确定递推函数
- 递推函数为前两情况的花费中最小的那个
dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2]+cost[i-2]
- 3. 初始化dp数组
- 由于可以从 前两个阶梯的任意一个开始,因此 初始化 dp[0] 和 dp[1] 都为 0。
- dp[0] = 0
- dp[1] = 0
- 4. 确定遍历顺序
- 从 i = 2 开始遍历,遍历到 n-1
2- 题解
⭐ 使用最小花费爬楼梯——题解思路
class Solution {
public int minCostClimbingStairs(int[] cost) {
// 1.定义dp数组
int[] dp = new int[cost.length+1];
// 确定递推公式 dp[i] = Math.min(dp[i-1],dp[i-2])
// 初始化
dp[0] = 0;
dp[1] = 0;
// 遍历顺序
for(int i = 2 ;i < cost.length+1;i++){
dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
}
return dp[cost.length];
}
}