企业官网建设流程全解析

​

DP 核心三要素：状态 dp [i]/dp [i][j]、状态转移、初始化 base case；

优化方向：滚动数组降维、空间压缩；

首先，怎么去判断一个问题是否是dp问题？

第一步：判断题目传达信号

1. 最大值、最小值

最大子数组、最小硬币、编辑距离、最大价值

2. 求方案总数、总共有多少种方法

爬楼梯多少种、目标和、零钱兑换多少组合

3. 问是否可达、能不能凑出来

分割等和子集，能否凑成sum/2

第二步： 检查两个核心性质（DP 必要条件）

1. 最优子结构
   一个大问题的最优解，可以由它子问题的最优解推导出来。
   大问题最优 ← 子问题最优。

例子：打家劫舍 n 间房子最大值，可以由 n‑1 和 n‑2 的最优结果推出来。
如果子问题最优，推不出全局最优 → 不能 DP，可以考虑贪心。

2. 重叠子问题

递归分解的时候，会反复算一模一样的子问题。暴力会重复计算。
比如爬楼梯 f (5)=f (4)+f (3)，f (4)=f (3)+f (2)，f (3) 被算了两次。
DP 就是开数组把 f (3) 结果存起来，避免重复。

如果子问题全部不重复（分治，例如归并排序），不需要 DP。

!!! 如果题目是求所有具体方案（全部集合），记住那是回溯不是dp; dp求的是数量最大最小是否可行；不需要输出全部路径；

for example:

1. 有多少种爬楼梯方式 dp✔

2. 全部爬楼梯的路径 回溯✔

第二步：检查两个核心性质（DP 必要条件）

① 最优子结构

一个大问题的最优解，可以由它子问题的最优解推导出来。
大问题最优 ← 子问题最优。

例子：打家劫舍 n 间房子最大值，可以由 n‑1 和 n‑2 的最优结果推出来。

如果子问题最优，推不出全局最优 → 不能 DP，可以考虑贪心。

② 重叠子问题

递归分解的时候，会反复算一模一样的子问题。暴力会重复计算。
比如爬楼梯 f (5)=f (4)+f (3)，f (4)=f (3)+f (2)，f (3) 被算了两次。
DP 就是开数组把 f (3) 结果存起来，避免重复。

如果子问题全部不重复（分治，例如归并排序），不需要 DP。

第三步：看决策：每一步有多条选择（选 / 不选；A/B/C 选择）

dp 题几乎都存在决策点：

• 背包：选这个物品 / 不选这个物品
• LIS：要不要把当前元素接到前面某个子序列后面
• 打家劫舍：偷当前房子 / 不偷当前房子
• 编辑距离：删除、插入、替换三选一

如果每一步只有唯一选择，没有多个决策，大概率贪心。

第四步：快速排除法

适合贪心，不适合 DP

局部最优可以直接得到全局最优。
比如：买卖股票 Ⅱ，每次能无限交易；区间选点。

贪心：每一步只看当下最好；DP：要保存所有子问题状态。

适合回溯 DFS

要求枚举全部具体方案，而不是求数量 / 最值。

子集、全排列，输出所有结果。如果题目改成求子集有多少种，那就可以 DP。

BFS

求最短路径、最少步数（无权图），BFS 更合适。

但是注意：有些题 BFS 和 DP 都可以解，比如零钱兑换。

第五步：一套实操判断流程（做题脑子里按顺序过）

拿到题目
1）看输出：求【最大 / 最小 / 方案数 / 是否可行】？
→ 不是，基本排除 DP；是，继续。

2）能否拆成规模更小的子问题？大问题依赖子问题结果？（最优子结构）
→ 不能，DP 不可用。

3）子问题有没有大量重复计算？（重叠子问题）
→ 有，适合 DP；没有考虑分治。

4）每一步是否存在多个决策？（选 / 不选，多种操作）
→ 有，DP 概率很大。

5）反例验证：贪心能不能直接做？

如果贪心试几个样例发现出错，那几乎确定 DP。

举例子对比：

例 1：零钱兑换：给定硬币，凑 amount 最少硬币。
贪心：[1,3,4], amount=6。贪心选 4+1+1（3 枚），最优是 3+3（2 枚）。贪心错，必须 DP。

例 2：爬楼梯：求多少种方案。
求数量；拆 f (n)=f (n‑1)+f (n‑2)；大量重复子问题；两种决策。DP。

例 3：最大子数组和：求最大；子问题是以 i 结尾最大值；决策接前面或者重新开始；DP。

第六步：判断出来是 DP 之后，下一步怎么思考？

1. 设计 dp 状态
   一维：dp [i]：前 i 个；或者以 i 结尾（子数组子序列）
   二维：dp [i][j]：两个序列前 i,j；区间 i~j；背包 i 物品 j 容量。

技巧：
✅子数组、子序列类：尽量定义为以 i 结尾，而不是前 i 个。转移会好写很多。

2. 写出 base case 初始化。（坑最多）
   求 max 初始 0；求 min 初始无穷 INF；计数题 dp [0]=1。
3. 根据决策写状态转移方程。（把每一种选择写出来 max/min 或者相加）
4. 确定遍历顺序。
   背包：0‑1 倒序，完全正序；区间 DP 先枚举区间长度；LIS i 从前往后，j < i。
5. 确定最终答案，注意是否取 dp 数组最大值，还是 dp [n]。

具体实战实例：

DP 题型维度梳理

说明：

• 一维 DP：主要使用一维数组dp[]；部分题目原始思考是二维，但可以空间压缩优化到一维。
• 二维 DP：必须二维数组dp[][]，很难压缩成干净一维（或者压缩后可读性极差，笔试一般直接写二维）。
• ⭐：可以优化为一维；原始状态是二维。
• 树 DP：不是一维也不是二维，是树上 DP，递归维护每个节点两个状态。

总结提炼（笔试记忆版）

纯一维 DP

1. 爬楼梯
2. 打家劫舍 Ⅰ、Ⅱ
3. LIS(300)
4. 最大子数组、乘积最大子数组
5. 解码方法 91

背包的 4 道题：理论原型二维，笔试全部写优化后的一维。

原生二维 DP

1. LCS 1143
2. 编辑距离 72
3. 股票 DP（原始二维，可以压缩变量）
4. 区间 DP：最长回文子序列 516
5. 正则匹配 10

特殊类型（不属于一维 / 二维数组 DP）

• 打家劫舍 Ⅲ：树 DP，递归，每个节点维护两个状态值。

容易混淆点（笔试坑）

1. 背包：原型二维，笔试一律写一维版本，浪费空间。
2. LCS、编辑距离虽然可以使用一维，但代码较为绕，笔试的话最好选择二维。
3. 区间 DP 一定二维，dp[i][j]代表 i 到 j 区间，没有一维写法。
4. 股票 dp [i][0]、dp [i][1]：第二维只有固定 2‑4 个状态，不是很大，可以压缩几个变量，但概念上属于二维 DP 思想。
5. LIS 是一维 dp 数组，但是内层还套一层 j 循环；数组维度不等于循环层数。

数组维度：看 dp 数组是几个下标dp[a]一维 /dp[a][b]二维；不是看你写几层 for 循环。

• 只和前几个元素有关：大多一维
• 两个序列互相匹配（s1 s2）：二维

下一章节进行实战practice!!!