Leetcode+Java+dpI

509.斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。
示例 1：
输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：
输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：
输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3
提示：
0 <= n <= 30

原理

问题分解：
斐波那契数列的计算具有 重叠子问题 和 最优子结构：
重叠子问题：计算 F(n) 需要 F(n-1) 和 F(n-2)，而 F(n-1) 又需要 F(n-2) 和 F(n-3)，以此类推，子问题会重复出现。
最优子结构：F(n) 可以直接由 F(n-1) 和 F(n-2) 的和构成。
直接递归计算（如 return fib(n-1) + fib(n-2)）会导致大量重复计算，时间复杂度为 O(2^n)，效率低下。
动态规划优化：
使用一个数组 dp 存储每个斐波那契数的值，dp[i] 表示 F(i)。
初始化：
dp[0] = 0（F(0) = 0）
dp[1] = 1（F(1) = 1）
状态转移：
对于 i ≥ 2，dp[i] = dp[i-1] + dp[i-2]，即第 i 个斐波那契数是前两个数的和。
通过迭代计算，从 i = 2 到 i = n，填充 dp 数组，最终 dp[n] 即为答案。
边界处理：
当 n < 2（即 n = 0 或 n = 1）时，直接返回 n，因为 F(0) = 0，F(1) = 1。
这避免了不必要的数组分配和循环。
时间和空间复杂度：
时间复杂度：O(n)，因为循环从 i = 2 到 n，执行 n-1 次迭代，每次操作是 O(1)。
空间复杂度：O(n)，因为使用了一个大小为 n+1 的 dp 数组。

代码

import java.util.*;class Solution {public int fib(int n) {// 边界条件：当 n < 2 时，F(0) = 0, F(1) = 1，直接返回 nif (n < 2) return n;// 创建 DP 数组，dp[i] 表示第 i 个斐波那契数int[] dp = new int[n + 1];// 初始化：F(0) = 0dp[0] = 0;// 初始化：F(1) = 1dp[1] = 1;// 从 i=2 开始计算每个斐波那契数// 根据公式 F(i) = F(i-1) + F(i-2)for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}// 返回第 n 个斐波那契数return dp[n];}
}

70.爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
提示：
1 <= n <= 45

原理

问题分解：
爬楼梯问题具有 重叠子问题 和 最优子结构：
重叠子问题：计算 dp[n] 需要 dp[n-1] 和 dp[n-2]，而 dp[n-1] 又需要 dp[n-2] 和 dp[n-3]，子问题会重复出现。
最优子结构：dp[n] 可以由 dp[n-1] 和 dp[n-2] 直接推导。
直接递归（如 return climbStairs(n-1) + climbStairs(n-2)）会导致大量重复计算，时间复杂度为 O(2^n)，对 n ≤ 45 会超时。
动态规划优化：
使用数组 dp 存储爬到每阶楼梯的方法数，dp[i] 表示爬到第 i 阶的方法数。
初始化：
dp[1] = 1：爬 1 阶只有 1 种方法（1 步）。
dp[2] = 2：爬 2 阶有 2 种方法（1+1 或 2）。
状态转移：
对于 i ≥ 3，dp[i] = dp[i-1] + dp[i-2]，表示爬到第 i 阶的方法数是爬到 i-1 阶和 i-2 阶的方法数之和。
通过迭代从 i = 3 到 n，填充 dp 数组，最终 dp[n] 即为答案。
边界处理：
当 n ≤ 2 时，直接返回 n，因为：
n = 1：dp[1] = 1（1 种方法）。
n = 2：dp[2] = 2（2 种方法）。
这避免了不必要的数组分配和循环。
时间和空间复杂度：
时间复杂度：O(n)，循环从 i = 3 到 n，执行 n-2 次迭代，每次操作是 O(1)。
空间复杂度：O(n)，使用大小为 n+1 的 dp 数组。

代码

import java.util.*;class Solution {public int climbStairs(int n) {// 边界条件：当 n <= 2 时，方法数等于 n（n=1 时 1 种，n=2 时 2 种）if (n <= 2) return n;// 创建 DP 数组，dp[i] 表示爬到第 i 阶楼梯的方法数int[] dp = new int[n + 1];// 初始化：爬到第 1 阶有 1 种方法（1 阶）dp[1] = 1;// 初始化：爬到第 2 阶有 2 种方法（1+1 或 2）dp[2] = 2;// 从 i=3 开始，计算每阶楼梯的方法数// 状态转移：dp[i] = dp[i-1] + dp[i-2]// 因为可以从 i-1 阶爬 1 步或从 i-2 阶爬 2 步到达 i 阶for (int i = 3; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}// 返回爬到第 n 阶的方法数return dp[n];}
}

746.使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。
示例 2：
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。
提示：
2 <= cost.length <= 1000
0 <= cost[i] <= 999

原理

问题分解：
问题具有 重叠子问题 和 最优子结构：
重叠子问题：计算 dp[i] 需要 dp[i-1] 和 dp[i-2]，子问题会重复出现。
最优子结构：到达第 i 阶的最低花费可以由前两阶的最优解推导。
直接递归（如 min(climb(i-1) + cost[i-1], climb(i-2) + cost[i-2])）会导致重复计算，时间复杂度为 O(2^n)，对 cost.length ≤ 1000 会超时。
动态规划优化：
使用数组 dp 存储到达每阶楼梯的最低花费，dp[i] 表示到达第 i 阶的最低花费。
初始化：
dp[0] = 0：从第 0 阶开始，无需支付费用。
dp[1] = 0：从第 1 阶开始，无需支付费用。
状态转移：
对于 i ≥ 2，dp[i] = min(dp[i-2] + cost[i-2], dp[i-1] + cost[i-1])。
表示从 i-2 阶爬 2 步（支付 cost[i-2]）或从 i-1 阶爬 1 步（支付 cost[i-1]），取最小值。
迭代从 i = 2 到 cost.length，填充 dp 数组，最终 dp[cost.length] 是到达楼顶的最低花费。
边界处理：
dp[0] = 0, dp[1] = 0 直接处理了从下标 0 或 1 开始的情况。
循环从 i = 2 开始，避免访问无效索引（cost[-1] 或 cost[0]）。
时间和空间复杂度：
时间复杂度：O(n)，其中 n = cost.length，循环从 i = 2 到 n，执行 n-1 次迭代，每次操作是 O(1)。
空间复杂度：O(n)，使用大小为 n+1 的 dp 数组。

代码

class Solution {public int minCostClimbingStairs(int[] cost) {// 创建 DP 数组，dp[i] 表示到达第 i 阶楼梯的最低花费// 数组大小为 cost.length + 1，因为可以到达楼顶（第 cost.length 阶）int[] dp = new int[cost.length + 1];// 初始化：从下标 0 或 1 开始，初始花费为 0dp[0] = 0; // 到达第 0 阶的花费为 0（起点）dp[1] = 0; // 到达第 1 阶的花费为 0（起点）// 从第 2 阶开始，计算到达每阶的最低花费// dp[i] = min(dp[i-2] + cost[i-2], dp[i-1] + cost[i-1])// 即从 i-2 阶爬 2 步或从 i-1 阶爬 1 步到达 i 阶，选择花费较小的for (int i = 2; i <= cost.length; i++) {dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);}// 返回到达楼顶（第 cost.length 阶）的最低花费return dp[cost.length];}
}