第10次内容

周子力大约 14 分钟教学文档算法设计与分析

上周回顾

二维DP

二维动态规划（2D DP）是动态规划中最常见且应用广泛的一种形式，其核心思想是将问题的解构建在一个二维状态表中，通过递推关系逐步填表，最终得到最优解。

回顾：

二维DP通常用于处理涉及两个序列、两个维度或两个决策变量的问题。其状态转移方程一般形如 dp[i][j] = f(dp[i-1][j], dp[i][j-1], dp[i-1][j-1], ...)，其中 i 和 j 分别代表两个维度的当前状态。典型的例子包括：

最长公共子序列（LCS）：dp[i][j] 表示第一个序列前 i 个字符与第二个序列前 j 个字符的最长公共子序列长度。
编辑距离：dp[i][j] 表示将第一个字符串的前 i 个字符转换为第二个字符串的前 j 个字符所需的最少操作数。
最小路径和：在二维网格中从左上角到右下角的最小代价路径。

思考与关键点：

状态定义是灵魂：清晰、无歧义地定义 dp[i][j] 的含义是解题的第一步，也是最关键的一步。它直接决定了状态转移方程的形式和正确性。例如，在LCS中，dp[i][j] 必须明确是“子序列”而非“子串”。
边界条件需严谨：二维DP的边界（如 dp[0][j] 和 dp[i][0]）往往代表其中一个维度为空的情况，必须根据问题语义仔细推导，否则会导致整个表格计算错误。
转移方向与依赖：必须确保在计算 dp[i][j] 时，其所依赖的前驱状态（如 dp[i-1][j], dp[i][j-1] 等）已经计算完成。这决定了遍历的顺序，通常是按行或按列从左到右、从上到下进行。
空间优化的可能性：由于 dp[i][j] 通常只依赖于当前行和上一行（或当前列和前一列），在很多情况下可以将空间复杂度从 O(mn) 优化到 O(min(m, n))，使用滚动数组技术。
从“长度”到“具体方案”：许多二维DP问题（如LCS）不仅要求计算最优值，还要求还原出具体的最优解（如公共子序列本身）。这需要在填表的同时记录决策路径（如使用方向数组），或在填表后进行回溯。
与一维DP的对比：二维DP的“状态空间”更大，能处理更复杂的多维依赖关系，但相应的，其时间与空间复杂度也更高。选择使用二维还是降维为一维，取决于问题的本质和约束条件。

总而言之，二维DP是连接理论与实践的桥梁。它要求我们不仅要理解递推关系，更要深刻把握问题的结构，并通过严谨的边界设定和有序的计算过程，将抽象的最优性原理转化为可执行的算法。掌握好二维DP，是解决复杂组合优化问题的重要基石。

动态规划（总结）

动态规划（Dynamic Programming，简称 DP）是一种用于求解具有最优子结构和重叠子问题性质的复杂问题的强大算法思想。它通过将原问题分解为相互关联的子问题，存储并重用子问题的解，从而避免重复计算，显著提高效率。

一、核心思想总结

最优子结构（Optimal Substructure）
问题的最优解包含其子问题的最优解。这意味着我们可以通过组合子问题的最优解来构造原问题的最优解。
重叠子问题（Overlapping Subproblems）
在递归求解过程中，某些子问题会被反复计算多次。DP 通过记忆化（自顶向下）或填表法（自底向上）存储已解决的子问题结果，实现“一次计算，多次使用”。
状态与状态转移
- 状态（State）：描述问题在某一阶段的特征，通常用一个或多个变量表示（如 dp[i]、dp[i][j]）。
- 状态转移方程（Recurrence Relation）：定义当前状态如何由先前状态推导而来，是 DP 的“灵魂”。
边界条件（Base Cases）
最小子问题的解，是递推的起点，必须准确设定，否则会导致整个 DP 表错误。

二、常见 DP 类型

类型	特点	典型问题
线性 DP	状态仅依赖前几个状态	最长递增子序列（LIS）、打家劫舍
区间 DP	状态表示区间 `[i, j]`	石子合并、矩阵连乘
二维/多维 DP	状态涉及多个维度	最长公共子序列（LCS）、编辑距离
树形 DP	状态定义在树的节点上	树的最大独立集、二叉树的直径
背包 DP	资源受限下的最优选择	0-1背包、完全背包、多重背包

三、设计 DP 的通用步骤

定义状态：明确 dp[...] 表示什么（“代表什么”比“怎么算”更重要）。
推导状态转移方程：分析当前状态如何由之前的状态转移而来。
确定初始条件和边界：处理最小规模问题。
确定计算顺序：确保在计算当前状态时，所需的历史状态已计算完毕。
空间与时间优化（可选）：如滚动数组、状态压缩等。

四、深入思考

DP 与贪心的区别：
贪心在每一步做局部最优选择，期望达到全局最优，但不保证正确性；DP 则通过穷举所有可能的子结构，确保全局最优，代价是更高的时空复杂度。
DP 与递归的关系：
朴素递归是“自顶向下+重复计算”，记忆化搜索是“自顶向下+缓存结果”，而标准 DP 是“自底向上+填表”。三者本质相通，实现方式不同。
构造解 vs. 求最优值：
很多题目不仅要求最优值（如 LCS 长度），还要求输出具体方案（如 LCS 字符串）。此时需在 DP 过程中记录决策路径（如通过 choice[i][j] 或回溯 dp 表）。
状态设计的艺术：
高效的 DP 往往依赖巧妙的状态定义。例如，在“买卖股票”系列中，通过引入“持有/不持有”状态，将看似复杂的问题简化为清晰的转移关系。
DP 的局限性：
状态空间过大（如指数级）会导致“维度灾难”；某些问题虽满足最优子结构，但子问题不重叠（如快排），则不适合用 DP。

五、结语

动态规划不仅是算法竞赛的核心技能，更是一种结构化思考复杂问题的思维方式。它教会我们：

“将大问题拆解为可管理的小问题，并通过系统性积累，最终构建全局最优解。”

掌握 DP，关键不在于背模板，而在于理解问题结构、精准定义状态、合理设计转移。随着练习深入，会逐渐培养出对“可DP性”的直觉——看到问题就能判断是否适合用 DP，并快速构思状态表示。

正如《算法导论》所言：“动态规划是一种方法，而不是一个公式。” 真正的 mastery，在于灵活运用其思想，而非机械套用。

本周内容

1. 买卖股票的最佳时机II

2. 贪心法的引入

一、从“买卖股票的最佳时机 II”看贪心思想

问题简述：
给定一个数组 prices，其中 prices[i] 表示第 i 天的股票价格。你可以进行任意多次交易（即买进后再卖出，再买进再卖出……），但不能同时参与多笔交易（必须在再次买入前卖出）。目标是最大化总利润。

贪心策略：
只要明天的价格比今天高，就今天买入、明天卖出。
即：收集所有价格上升的“正收益”段。

例如：
prices = [1, 2, 3, 4]

第1天买，第4天卖：利润 = 3
或：(1→2) + (2→3) + (3→4) = 1 + 1 + 1 = 3 —— 结果相同

关键洞察：

股价连续上涨的区间，无论拆成多次交易还是一次交易，总利润都等于首尾之差，而拆分成每天“低买高卖”等价于累加所有相邻正差值。

因此，我们只需遍历一次数组，累加所有 prices[i] - prices[i-1] > 0 的差值，即可得到最大利润。

def maxProfit(prices):
    profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i-1]:
            profit += prices[i] - prices[i-1]
    return profit

这一策略不考虑未来所有可能的组合，而是在每一步都做出“当前看起来最优”的选择（只要有正收益就立刻交易），却最终得到了全局最优解。这就是贪心法的典型体现。

二、贪心算法的定义

贪心算法（Greedy Algorithm） 是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略。

它不回溯，不做全局搜索，而是“走一步看一步”，每一步都追求局部最优。
它通常高效（时间复杂度低，常为线性或对数级），但并不总能得到全局最优解。
只有当问题具备特定性质时，贪心策略才有效（即局部最优能导出全局最优）。

三、贪心算法的核心性质

要判断一个问题是否可以用贪心法正确求解，通常需要满足以下两个关键性质：

1. 贪心选择性质（Greedy Choice Property）

可以通过局部最优（贪心）选择来构造全局最优解。
即：在每一步，做出当前看起来最好的选择后，剩下的子问题仍能与该选择组合成原问题的最优解。

在“买卖股票 II”中：只要明天价格更高，今天买入明天卖出就是当前最优选择，且不影响后续最优交易的进行。

2. 最优子结构性质（Optimal Substructure）

一个问题的最优解包含其子问题的最优解。
（注意：这一性质也是动态规划的前提，但贪心对子问题的依赖更“短视”）

在本题中：总最大利润 = 所有正收益天数的利润之和，而每一天的决策独立、可叠加。

四、贪心法 vs. 动态规划

特性	贪心算法	动态规划
决策方式	局部最优，不可回溯	考虑所有可能，保留最优
是否保证最优	仅在满足贪心性质时保证	一般能保证（若状态设计正确）
时间复杂度	通常较低（O(n)、O(n log n)）	较高（O(n²)、O(nm) 等）
空间复杂度	通常 O(1)	常需额外空间存状态
典型问题	区间调度、找零钱（某些面额）、股票 II	背包、LCS、股票含冷冻期等

关键区别：
贪心是“近视但高效”的策略，只相信“眼前最优”；
动态规划是“深谋远虑”的策略，通过记忆和组合保障全局最优。

五、总结

“买卖股票的最佳时机 II”之所以能用贪心法高效求解，是因为其利润具有可分解性和无后效性——任意一段上涨行情都可以拆分为相邻天的正收益，且今天的交易决策不影响未来可获得的利润结构。

这体现了贪心法的精髓：

在具备贪心选择性质的问题中，一次次“短视”的最优决策，竟能奇迹般地汇聚成全局最优解。

正如一句算法箴言：
“不是所有问题都值得深思熟虑，有些只需抓住每一个微小的机会。”

目标：通过多次买卖（不能同时持有多股），最大化总利润。
贪心策略：只要明天价格高于今天，就今天买入、明天卖出。
本质：收集所有正向价格差，即所有“上升沿”。
关键观察：利润具有可加性和无交互性——任意两天之间的上涨利润可分解为连续日的正收益之和，且交易之间互不干扰。

2. 跳跃游戏（Jump Game）

目标：判断是否能从数组首部跳到末尾（每个位置的值表示最大跳跃长度）。
贪心策略：维护一个变量 max_reach，表示当前能到达的最远位置。遍历过程中不断更新 max_reach = max(max_reach, i + nums[i])。若某时刻 i > max_reach，则无法继续；若最终 max_reach >= n-1，则可达。
本质：不关心具体怎么跳，只关心“最远能到哪”。
关键观察：能到达更远的位置，意味着拥有更多未来选择权，因此“尽可能跳得远”是安全且最优的局部决策。

二、贪心思想的共性提炼

尽管问题不同，但二者体现的贪心思维高度一致：

维度	买卖股票 II	跳跃游戏	共性
局部决策依据	今天是否能赚（price[i] > price[i-1]）	当前能否扩展最远可达范围	基于当前信息做“最有利”选择
状态维护	累计利润	最远可达位置（max_reach）	仅维护一个关键状态变量
无后效性	今日交易不影响未来交易结构	能跳到某位置，后续选择与如何到达无关	历史路径不重要，只看当前状态
全局最优来源	所有局部正收益之和	通过不断扩展可达边界最终覆盖终点	局部最优的累积 = 全局最优

✅ 二者都满足：局部最优选择不会导致全局次优，即具备贪心选择性质。

三、贪心法的深层思考

1. “看不见未来”也能成功？

贪心算法不预知未来，却在这些问题中“恰好”成功。其背后逻辑是：

问题结构具有“单调性”或“累积性”：
- 股票：利润可线性叠加，无耦合。
- 跳跃：可达性具有传递性（A→B→C ⇒ A→C），且“更远”永远优于“更近”。

贪心不是“盲目乐观”，而是对问题数学结构的信任。

2. 贪心 vs. 动态规划：问题敏感性差异

若将“买卖股票 II”改为含交易手续费或冷冻期，贪心失效，必须用 DP（因为交易之间产生耦合，局部决策影响未来成本）。
若将“跳跃游戏”改为求最少跳跃次数（Jump Game II），贪心仍可用，但策略需调整为“在当前可达范围内，选择能跳最远的下一步”——这仍是贪心，但更精细。

贪心对问题约束极其敏感。微小改动（如加入状态依赖）可能使其失效。

3. 贪心的“视野”：维护什么状态？

股票问题维护的是结果量（利润）；
跳跃问题维护的是能力边界（最远位置）。

这提示我们：设计贪心算法的关键，是识别出那个能代表“当前最优潜力”的状态变量。找到它，问题就迎刃而解。

四、总结：贪心法的哲学启示

“在合适的土壤中，局部最优的种子终将长成全局最优的参天大树。”

适用条件苛刻：只有当问题具备贪心选择性质与最优子结构时，贪心才有效。
效率与简洁：一旦适用，贪心往往以 O(n) 时间、O(1) 空间给出优雅解。
思维训练价值：分析为何贪心在此成立，能加深对问题内在结构的理解。

买卖股票 II 教会我们：抓住每一个微小的上升机会，终将累积成最大收益；
跳跃游戏 告诉我们：不必规划每一步，只需确保自己始终站在所能到达的最前沿。

二者共同诠释了贪心法的精髓：

在不确定的世界里，做当下最不后悔的选择。