讨论 7

(a) 对于「隔位种树」算法，一个简单的反例输入是 \([2, 1, 1, 2]\)。此时最优解是在坑位 \(1\) 和 \(4\) 种树。对于贪心算法（每次选最大的 \(x_i\)），一个简单的反例输入是 \([2, 3, 2]\)。此时贪心算法会在坑位 \(2\) 种树，但最优解是在坑位 \(1\) 和 \(3\) 种树。

(b) \(f(1) = x_1\)，\(f(2) = \max\{x_1, x_2\}\)。

(c) 如果不在坑位 \(i\) 种树，那么在坑位 \(1\) 到 \(i\) 种树的最优方式，等同于在坑位 \(1\) 到 \(i-1\) 种树的最优方式。因此，\(f(i) = f(i-1)\)。

(d) 如果在坑位 \(i\) 种树，那么我们会从该树获得 \(x_i\) 个苹果。然而，我们无法在坑位 \(i-1\) 种树，因此只允许在坑位 \(1\) 到 \(i-2\) 种树。于是，我们可以选取在坑位 \(1\) 到 \(i-2\) 种树的最优方式，再在该方案基础上加上坑位 \(i\) 的一棵树，从而得到在坑位 \(1\) 到 \(i\) 种树的最优方式。因此 \(f(i) = f(i-2) + x_i\)。

(e) 初始化一个长度为 \(n\) 的数组，其中第 \(i\) 个元素将存储 \(f(i)\)。先填入 \(f(1)\)，然后按顺序使用公式 \(f(i) = \max\{f(i-1), x_i + f(i-2)\}\) 填满表格的其余部分。最后返回表格中的 \(f(n)\)。

算法描述：

• 子问题定义：\(dp[i]\) 表示以索引 \(i\) 结尾（非空）的最大和子数组。

• 基本情况：\(dp[0] = A[0]\)

• 递推关系：我们按 \(i\) 递增的顺序计算 \(dp\) 值（\(i = 1, \ldots, n-1\)），递推式为 \(dp[i] = \max(0, dp[i-1]) + A[i]\)。

• 最终答案：输出最大的 \(dp[i]\)，若为负数则输出 \(0\)。

以下是说明该算法的伪代码：

def max_subarray_sum(A): n = len(A) dp = [0 for i in range(n)] # 基本情况 dp[0] = A[0] # 使用动态规划计算 dp 数组的其余部分 for i in range(1, n): dp[i] = max(0, dp[i-1]) + A[i] return max(max(dp), 0)

注意，此解法使用 \(O(n)\) 空间，因为需要存储整个 \(dp\) 数组。然而，计算某个 \(dp[i]\) 时只用到前一项 \(dp[i-1]\)，因此可以通过仅维护一个「滚动和」来优化空间复杂度：

def max_subarray_sum(A): n = len(A) # 基本情况 max_sub_sum = running_sum = A[0] # 使用动态规划计算 dp 数组的其余部分 for i in range(1, n): running_sum = max(0, running_sum) + A[i] max_sub_sum = max(max_sub_sum, running_sum) return max(max_sub_sum, 0)

此解法使用 \(O(1)\) 空间，因为只需维护三个整数 \(n\)、\(max\_sub\_sum\) 和 \(running\_sum\)！（注意：在确定空间复杂度时不计入输入 \(A\) 的空间。）

另外，如果你做过很多 LeetCode 题目，可能会认出这就是 Kadane 算法。

正确性证明：使用归纳法证明对所有 \(i \ge 0\)，\(dp[i]\) 都是正确的。

• 基本情况（\(i = 0\)）：只有一个元素时，唯一的子数组选项是 \(A[0]\)。

• 归纳假设（\(i = k\)）：假设 \(dp[k]\) 是以索引 \(k\) 结尾的最大和子数组的正确值。

• 归纳步骤（\(i = k \Rightarrow i = k+1\)）：计算 \(dp[k+1]\) 时，我们要么使用 \(dp[k]\)，要么忽略它（重新开始一个子数组和）。分两种情况：

• 当 \(dp[k] \ge 0\) 时，最优策略是使用它并加上 \(A[k+1]\)，以期最大化 \(dp[k+1]\)。

• 当 \(dp[k] < 0\) 时，最优策略是丢弃它，直接从 \(k+1\) 开始一个新的子数组和。因为若 \(dp[k] < 0\)，则 \(dp[k] + A[k+1] < 0 + A[k+1] = A[k+1]\)。

两种情况总结如下：

\[ dp[k+1] = \begin{cases} dp[k] + A[k+1] & dp[k] \ge 0 \\ A[k+1] & dp[k] < 0 \end{cases} = \max(dp[k], 0) + A[k+1] \]

这正是我们的递推关系。

运行时间分析：由于我们执行 \(O(n)\) 次常数时间操作，总体运行时间为 \(O(n)\)。

(a) 对 \(0 \le w \le W\)，定义

\[ f(w) = \text{凑出金额 } w \text{ 所需的最少硬币数量。} \]

它满足

\[ f(w) = \begin{cases} 0 & \text{若 } w = 0, \\ 1 + \min_{j: v_j \le w} f(w - v_j) & \text{若 } w > 0, \\ \infty & \text{若无法凑出} \end{cases} \]

答案是 \(f(W)\)，其中 \(\infty\) 表示不可能。时间复杂度为 \(O(nW)\)。

(b) 对 \(0 \le i \le n\) 和 \(0 \le w \le W\)，定义

\[ f(i, w) = \text{使用前 } i \text{ 枚硬币凑出金额 } w \text{ 所需的最少硬币数量（每种面额仅一枚）。} \]

它满足

\[ f(i, w) = \begin{cases} 0 & \text{若 } i = 0 \text{ 且 } w = 0, \\ f(i-1, w) & \text{若 } i > 0, \\ 1 + f(i-1, w - v_i) & \text{若 } i > 0 \text{ 且 } v_i \le w, \\ \infty & \text{否则} \end{cases} \]

问题的答案是 \(f(n, W)\)。时间复杂度为 \(O(nW)\)。

核心思路：我们创建一个递归公式，其中对每个长度为 \(k\) 的子问题，选择切割长度 \(i\)，使得 \(Price(i) + Value(k-i)\) 最大化。这里 \(Price(i)\) 是出售长度为 \(i\) 的整根管件的价格，\(Value(k-i)\) 是长度为 \(k-i\) 的管件经过最优切割后获得的价值。

def cutPipe(price, n): val = [0 for x in range(n+1)] val[0] = 0 # 自底向上构建 val[] 表格并返回表中最后一项 for i from 1 to n: max_val = 0 for j from 0 to i-1: max_val = max(max_val, price[j] + val[i-j-1]) val[i] = max_val return val[n]

证明：对铜管长度进行归纳，可证明解的正确性。设 \(cutPipe(n)\) 为长度为 \(n\) 的管件的最优解。基本情况：若管件长度为 \(1\)，则 \(cutPipe(1) = Price(1) = Val(1)\)。归纳：假设对所有长度小于等于 \(k\) 的管件都已找到最优价格。若算法第一次切割 \(x_1\) 不是最优的，则存在 \(x'_1\) 使得 \(Val((k+1) - x_1) + Price(x_1) < Val((k+1) - x'_1) + Price(x'_1)\)。由归纳假设，这意味着 \(cutPipe((k+1) - x_1) + Price(x_1) < cutPipe((k+1) - x'_1) + Price(x'_1)\)。因此算法必然选择了 \(x'_1\) 而非 \(x_1\)（矛盾）。因此，由归纳法可知，对所有 \(n > 0\)，\(cutPipe(n) = Val(n)\)。

运行时间：算法包含两层嵌套 for 循环，运行时间为 \(O(n^2)\)。