基础 DP 问题
入门级 DP 问题，帮助理解核心思想。
1. 斐波那契数列
问题
F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)
解法对比
typescript
// ❌ 递归 - 指数级复杂度，有大量重复计算
function fib1(n: number): number {
if (n <= 1) return n;
return fib1(n - 1) + fib1(n - 2);
}
// ✅ DP 自底向上 - O(n) 时间, O(1) 空间
function fib2(n: number): number {
if (n <= 1) return n;
let prev = 0, curr = 1;
for (let i = 2; i <= n; i++) {
[prev, curr] = [curr, prev + curr];
}
return curr;
}
// ✅ DP 记忆化递归 - O(n) 时间, O(n) 空间
function fib3(n: number, memo: number[] = []): number {
if (n <= 1) return n;
if (memo[n]) return memo[n];
memo[n] = fib3(n - 1, memo) + fib3(n - 2, memo);
return memo[n];
}复杂度对比
| 方法 | 时间 | 空间 |
|---|---|---|
| 递归 | O(2^n) | O(n) |
| 记忆化 | O(n) | O(n) |
| 迭代 | O(n) | O(1) |
2. 爬楼梯
问题
- 每次爬 1 或 2 级台阶，到第 n 级有多少种方法？
状态转移
typescript
// dp[i] = 到达第 i 级的方法数
// dp[i] = dp[i-1] + dp[i-2]
function climbStairs(n: number): number {
if (n <= 2) return n;
let dp = [0, 1, 2];
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// 空间优化
function climbStairsOptimized(n: number): number {
if (n <= 2) return n;
let prev = 1, curr = 2;
for (let i = 3; i <= n; i++) {
[prev, curr] = [curr, prev + curr];
}
return curr;
}扩展
变体
- 每次爬 1, 2, 或 3 级 →
dp[i] = dp[i-1] + dp[i-2] + dp[i-3] - 每步代价不同 → 变成最小花费爬楼梯
3. 最小花费爬楼梯
问题
- 每层楼梯有 cost，爬到顶的最小花费
解法
typescript
function minCostClimbingStairs(cost: number[]): number {
const n = cost.length;
// dp[i] = 到达第 i 级的最小花费
// dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
let dp0 = 0, dp1 = 0; // dp[0], dp[1]
for (let i = 2; i <= n; i++) {
const dpi = Math.min(dp1 + cost[i - 1], dp0 + cost[i - 2]);
dp0 = dp1;
dp1 = dpi;
}
return dp1;
}4. 打家劫舍 I
问题
- 不能偷连续两间房，最多能偷多少钱
解法
typescript
function rob(nums: number[]): number {
const n = nums.length;
if (n === 0) return 0;
if (n === 1) return nums[0];
// dp[i] = 前 i 间房能偷的最大金额
// dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])
let prev2 = 0, prev1 = nums[0];
for (let i = 1; i < n; i++) {
const curr = Math.max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}图解状态转移
房间: [2, 7, 9, 3, 1]
索引: 0 1 2 3 4
dp[0] = 2 (偷第0间)
dp[1] = max(2, 7) = 7 (偷第1间)
dp[2] = max(7, 2+9) = 11 (偷第0+2间)
dp[3] = max(11, 7+3) = 11 (偷第0+2间)
dp[4] = max(11, 11+1) = 12 (偷第0+2+4间)复杂度分析
| 方法 | 时间 | 空间 |
|---|---|---|
| 二维 DP | O(n) | O(n) |
| 空间优化 | O(n) | O(1) |
5. 打家劫舍 II（环形房屋）
问题
- 房屋围成一圈，首尾相连，不能偷相邻房屋
核心思路
将环形问题拆分为两个线性问题：
情况1: 偷 [0, n-1) → 不偷最后一间
情况2: 偷 [1, n) → 不偷第一间
答案 = max(情况1, 情况2)解法
typescript
function robII(nums: number[]): number {
const n = nums.length;
if (n === 0) return 0;
if (n === 1) return nums[0];
if (n === 2) return Math.max(nums[0], nums[1]);
// 情况1: 不偷最后一间 (0 到 n-2)
const robRange = (start: number, end: number): number => {
let prev2 = 0, prev1 = 0;
for (let i = start; i <= end; i++) {
const curr = Math.max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = curr;
}
return prev1;
};
return Math.max(
robRange(0, n - 2), // 不偷最后一间
robRange(1, n - 1) // 不偷第一间
);
}为什么不能直接用打家劫舍 I？
错误做法: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
问题: 房屋0和房屋n-1相邻
↙ ↘
[0] ... [n-1]
如果偷了0，就不能偷n-1
dp会错误地允许同时偷0和n-16. 打家劫舍 III（二叉树）
问题
- 二叉树形状的房屋，不能偷相邻节点
解法（树形 DP + 记忆化）
typescript
function robIII(root: TreeNode | null): number {
const dfs = (node: TreeNode | null): [notRob: number, rob: number] => {
if (!node) return [0, 0];
const [leftNotRob, leftRob] = dfs(node.left);
const [rightNotRob, rightRob] = dfs(node.right);
// 不偷当前节点 = 左右子树各自最优
const notRob = leftRob + rightRob;
// 偷当前节点 = 不偷左右子树的根节点 + 当前值
const rob = node.val + leftNotRob + rightNotRob;
return [notRob, rob];
};
const [notRob, rob] = dfs(root);
return Math.max(notRob, rob);
}状态定义
| 状态 | 含义 |
|---|---|
notRob | 以该节点为根的子树，不偷该节点的最大收益 |
rob | 以该节点为根的子树，偷该节点的最大收益 |
树形 DP 图解
3
/ \
2 3
\ \
3 1
返回: [不偷根, 偷根]
节点3: [3, 3+2+3=8]
节点2: [0, 2]
节点3: [1, 3+1=4]
根节点: max(8, 4+3=7) = 87. 跳跃游戏 I
问题
- 数组
nums[i]表示从位置i最远能跳到i + nums[i] - 能否跳到最后一个位置？
解法
typescript
// 方法1: DP（超时风险）
function canJump(nums: number[]): boolean {
const n = nums.length;
const dp = Array(n).fill(false);
dp[0] = true;
for (let i = 0; i < n; i++) {
if (!dp[i]) continue;
for (let j = 1; j <= nums[i] && i + j < n; j++) {
dp[i + j] = true;
}
}
return dp[n - 1];
}
// 方法2: 贪心（最优）
function canJumpGreedy(nums: number[]): boolean {
let maxReach = 0;
for (let i = 0; i < nums.length; i++) {
if (i > maxReach) return false; // 到不了位置 i
maxReach = Math.max(maxReach, i + nums[i]);
if (maxReach >= nums.length - 1) return true;
}
return true;
}贪心核心思想
位置: 0 1 2 3 4
nums: [2, 3, 1, 1, 4]
reach: 2 4 4 4 5
step 0: maxReach = 0+2 = 2
step 1: maxReach = max(2, 1+3) = 4
step 2: i=2 <= maxReach=4 ✓
step 3: i=3 <= maxReach=4 ✓
step 4: maxReach >= n-1 ✓8. 跳跃游戏 II（最小跳跃次数）
问题
- 同上，但要求最小跳跃次数
解法
typescript
function jump(nums: number[]): number {
let jumps = 0;
let curEnd = 0; // 当前跳跃能到达的边界
let farthest = 0; // 所有位置能达到的最远距离
for (let i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
// 到达当前跳跃的边界，需要再跳一次
if (i === curEnd) {
jumps++;
curEnd = farthest;
}
}
return jumps;
}图解
nums: [2, 3, 1, 1, 4]
i=0: farthest=2, curEnd=0, 跳!
jumps=1, curEnd=2
i=1: farthest=4
i=2: farthest=4, 到达边界 curEnd=2, 再跳!
jumps=2, curEnd=4
i=3: farthest=4
i=4: 到达终点
最小跳跃次数: 2关键理解
curEnd: 当前这一次跳跃能达到的最远范围farthest: 在 curEnd 范围内，所有位置能达到的最远- 当 i 到达 curEnd，意味着需要开始下一次跳跃
9. 等差数列划分
问题
- 统计数组中所有等差子数组的数量
typescript
function numberOfArithmeticSlices(nums: number[]): number {
const n = nums.length;
if (n < 3) return 0;
let count = 0;
let dp = 0; // 以 nums[i-2], nums[i-1], nums[i] 结尾的等差数列数
for (let i = 2; i < n; i++) {
if (nums[i] - nums[i - 1] === nums[i - 1] - nums[i - 2]) {
dp = dp + 1; // 新的等差数列可以扩展旧的
count += dp;
} else {
dp = 0; // 重置
}
}
return count;
}状态转移理解
nums: [1, 2, 3, 4]
i=2: [1,2,3] 是等差 → dp=1, count=1
i=3: [2,3,4] + 扩展 [1,2,3,4] → dp=2, count=3
^^^^^^^^
新增的等差子数组
等差子数组: [1,2,3], [2,3,4], [1,2,3,4][!summary] 一维 DP 通用模板
typescript// 基础模板 let dp0 = initial0, dp1 = initial1; for (let i = 2; i <= n; i++) { dpi = max/min(dp[i-1], dp[i-2] + cost[i]); dp0 = dp1; dp1 = dpi; } // 环形处理: 拆分为两个线性问题 // 树形处理: 返回 [不选, 选] 两个状态 // 跳跃问题: 用 curEnd + farthest 模拟
参见: **DP算法索引**