两类"最优化"问题
信息学竞赛里有一大类题叫"最优化问题"：在众多方案里找出最优的那个。比如用最少的硬币凑出某个金额、安排最多的活动、走最短的路径。
解决最优化问题有两大主流思想：贪心和动态规划。前者像"走一步看一步"，后者像"提前把每一步都算清楚"。这篇文章用孩子能懂的方式，把两种思想讲透。
贪心赌当下，DP 算全局——理解两者的差别，就抓住了算法的钥匙。
- 贪心局部最优推全局最优。
- DP子问题答案存表复用。
- 状态转移DP 的核心方程。
- 适用性贪心有前提，DP 更通用。
贪心思想：每一步都选当下最好
贪心算法的思路很简单：每一步都做当前看起来最优的选择，不做回头路，赌这些局部最优加起来就是全局最优。
生活例子：找零钱时先给最大面额的，就是贪心。它的优点是快——不枚举所有方案，一次扫描就出结果。
但贪心不是万能药，它要求问题有"贪心选择性质"：局部最优确实能推出全局最优。
经典贪心：活动安排与零钱兑换
活动安排：一天有多场活动，每场有开始和结束时间，问最多能参加几场。贪心策略：按结束时间排序，每次都选结束最早且不与已选冲突的活动——这是最经典、证明最清晰的贪心题。
零钱兑换（特定面额）：硬币面额 1、5、10、25，凑 63 元。贪心：先拿 25×2，再 10×1，再 5×0，最后 1×3，共 6 枚。这种面额下贪心是对的。
coins = [25, 10, 5, 1]
amount = 63
count = 0
for c in coins:
count += amount // c
amount %= c
print(count) # 6贪心的局限：什么时候会错
把硬币面额改成 1、3、4，凑 6 元：贪心会拿 4+1+1 共 3 枚，但最优其实是 3+3 共 2 枚——贪心错了。
这就是贪心的陷阱：看起来每一步都对，全局却不是最优。遇到这种问题，就需要动态规划。
贪心错一次，就知道自己面对的是 DP 题。
动态规划：记下子问题的答案
动态规划（DP）的思路：把大问题拆成小问题，先算小问题的答案并记在表里，再用小问题的答案拼出大问题的答案。核心是状态转移方程。
拿"爬楼梯"举例：一次能爬 1 级或 2 级，爬到第 n 级有几种方法？到第 n 级 = 到第 n-1 级的方法数 + 到第 n-2 级的方法数。这就是状态转移方程：f(n) = f(n-1) + f(n-2)。
def climb(n):
f = [0] * (n + 1)
f[0], f[1] = 1, 1
for i in range(2, n + 1):
f[i] = f[i-1] + f[i-2]
return f[n]
print(climb(5)) # 8经典 DP：爬楼梯与背包
0-1 背包问题：有若干物品，每个有重量和价值，背包有容量限制，问能装的最大总价值。思路：dp[i][w] 表示前 i 个物品、容量 w 时的最大价值；每个物品要么不拿、要么拿，取两者较大。
def knapsack(weights, values, cap):
n = len(weights)
dp = [[0] * (cap + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(cap + 1):
if weights[i-1] <= w:
dp[i][w] = max(dp[i-1][w],
dp[i-1][w-weights[i-1]] + values[i-1])
else:
dp[i][w] = dp[i-1][w]
return dp[n][cap]背包问题是 DP 的经典入口，信息学竞赛的入门必学。
怎么判断用贪心还是 DP
判断口诀：
- 能证明局部最优即全局最优：用贪心（活动安排、部分找零）。
- 子问题有重叠、需要记表：用 DP（背包、爬楼梯、最长公共子序列）。
- 不确定：先用贪心写，再自己举反例；举出反例就换 DP。
练手建议：先写活动安排（贪心），再写爬楼梯（DP），最后挑战 0-1 背包——这三道题能把今天学的思想钉牢。
- 贪心快但有前提。
- DP慢一点但通用。
- 状态转移是 DP 的灵魂。
- 举反例是区分两者的好办法。