[!info] related notes 算法面试题型 MOC 动态规划 爬楼梯 打家劫舍 最长递增子序列

线性 DP

一句话

状态沿数组下标从左到右推进，dp[i] 通常只依赖前面若干个状态。

一页式速查表

小类	常见状态	转移关键词	入门题	进阶题
前 i 个元素	dp[i]	选 / 不选	[[house-robber	打家劫舍]]
以 i 结尾	dp[i]	枚举最后一个	[[longest-increasing-subsequence	LIS]]
固定前几个状态	dp[i] / 若干变量	来自 i-1、i-2	[[climbing-stairs	爬楼梯]]

什么时候想到它

• 题目对象是数组 / 一维字符串
• 当前决策只和前面几个位置有关
• 要求最大值、最小值、方案数、可行性

常见识别信号：

• “走到第 i 步”
• “考虑前 i 个元素”
• “以 i 结尾”

两种最常见状态设计

1. 前 i 个元素

适合“选或不选”：

dp[i] = 前 i 个元素中的最优值 / 方案数

例子：打家劫舍。

2. 以 i 结尾

适合“枚举最后一个”：

dp[i] = 以第 i 个元素结尾的最优值

例子：最长递增子序列、最大子数组和。

通用模板

const dp = new Array(n).fill(0);

// 处理边界
dp[0] = ...;

for (let i = 1; i < n; i++) {
    dp[i] = ...; // 从更小状态转移
}

return dp[n - 1];

如果状态定义是“前 i 个元素”，也常写成：

const dp = new Array(n + 1).fill(0);

for (let i = 1; i <= n; i++) {
    dp[i] = ...;
}

代表题 1：爬楼梯

题目：[[climbing-stairs|爬楼梯]]

状态

dp[i] 表示到达第 i 阶的方法数。

转移

• 最后一步走 1 阶：来自 dp[i - 1]
• 最后一步走 2 阶：来自 dp[i - 2]

所以：

dp[i] = dp[i - 1] + dp[i - 2]

样例

n = 5

• dp[1] = 1
• dp[2] = 2
• dp[3] = 3
• dp[4] = 5
• dp[5] = 8

代表题 2：打家劫舍

题目：打家劫舍

状态

dp[i] 表示考虑前 i + 1 个房子时的最大收益。

转移

• 不偷当前房子：dp[i - 1]
• 偷当前房子：dp[i - 2] + nums[i]

所以：

dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

样例

nums = [2, 7, 9, 3, 1]

• dp[0] = 2
• dp[1] = 7
• dp[2] = 11
• dp[3] = 11
• dp[4] = 12

答案是 12。

高频坑

• dp[i] 到底是“前 i 个”还是“以 i 结尾”没写清楚
• 边界条件漏掉 i = 0 / i = 1
• 明明只依赖前两个状态，却还开大数组，没有做空间优化

记忆口诀

• 选 / 不选 -> 想“前 i 个”
• 接在谁后面 -> 想“以 i 结尾”

推荐继续练

• 爬楼梯
• 打家劫舍
• 打家劫舍 II
• 最长递增子序列
• 最长有效括号