Skip to content

8 Dynamic Programming

动态规划问题识别

Which one of the following problems can be best solved by dynamic programming?

\(\textnormal{A}\). Mergesort \(\qquad\) \(\textnormal{B}\). Closest pair of points problem

\(\textnormal{C}\). Quicksort \(\qquad\) \(\textnormal{D}\). Longest common subsequence problem

答案

\(\textnormal{D}\)

基本性质

Which of the following is one of the basic elements of dynamic programming algorithm.

\(\textnormal{A}\). Define the optimal solution

\(\textnormal{B}\). Constructing the optimal solution

\(\textnormal{C}\). Calculate the optimal solution

\(\textnormal{D}\). Overlapping properties of subproblems

答案

动态规划的问题特性：

  • 重叠子问题：动态规划的子问题是相互依赖的（而分治算法处理的是独立的子问题）
  • 最优子结构：原问题的最优解是从子问题的最优解构建得来的
  • 无后效性：给定一个确定的状态，它的未来发展只与当前状态有关，而与过去经历的所有状态无关（否则难以用动态规划解决）

故答案为 \(\textnormal{D}\)

Which of the following is the key prerequisite for a problem to be solvable by both dynamic programming algorithm and greedy algorithm?

\(\textnormal{A}\). Greedy choice property

\(\textnormal{B}\). Overlapping subproblems

\(\textnormal{C}\). Optimal substructure property

\(\textnormal{D}\). Defining the optimal solution

答案
  • 动态规划（DP）的核心依赖：最优子结构 + 重叠子问题
  • 贪心算法的核心依赖：最优子结构 + 贪心选择性质；

故答案为 \(\textnormal{C}\)

If a problem can be solved by dynamic programming, it must be solved in polynomial time.

答案

动态规划的时间复杂度由子问题数量和每个子问题的求解时间决定，若子问题数量是指数级，则动态规划也为指数时间，故答案为 \(\textnormal{F}\)

依赖问题

Given a recurrence equation \(f_{i,j,k} = f_{i,j+1,k} + \min_{0 \leq l \leq k} \{ f_{i-1,j,l} + w_{j,l} \}\). To solve this equation in an iterative way, we cannot fill up a table as follows:

\(\textnormal{A}\). for k in 0 to n: for i in 0 to n: for j in n to 0

\(\textnormal{B}\). for i in 0 to n: for j in 0 to n: for k in 0 to n

\(\textnormal{C}\). for i in 0 to n: for j in n to 0: for k in n to 0

\(\textnormal{D}\). for i in 0 to n: for j in n to 0: for k in 0 to n

答案

对于给定递推方程 \(f_{i,j,k} = f_{i,j+1,k} + \min_{0 \leq l \leq k} \{ f_{i-1,j,l} + w_{j,l} \}\)，明确以下依赖：

  • 对 \(j\) 的依赖：\(f_{i,j,k}\) 依赖于 \(f_{i,j+1,k}\)，因此 \(j\) 必须从大到小循环（确保 \(j+1\) 先于 \(j\) 被计算）
  • 对 \(i\) 的依赖：\(f_{i,j,k}\) 依赖于 \(f_{i-1,j,l}\)，因此 \(i\) 必须从小到大循环（确保 \(i-1\) 先于 \(i\) 被计算）
  • 对 \(k\) 的依赖：\(\min_{0 \leq l \leq k}\) 要求 \(l\) 从 \(0\) 到 \(k\) 的状态已被计算

故答案为 \(\textnormal{B}\)

To solve the optimal binary search tree problem, we have the recursive equation \(c_{ij} = \min_{i \le l \le j} \{w_{ij} + c_{i,l-1}+c_{l+1,j}\}\). To solve this equation in an iterative way, we must fill up a table as follows:

\(\textnormal{A}\). for i= 1 to n-1 do; for j= i to n do; for l= i to j do

\(\textnormal{B}\). for j= 1 to n-1 do; for i= 1 to j do; for l= i to j do

\(\textnormal{C}\). for k= 1 to n-1 do; for i= 1 to n-k do; set j = i+k; for l= i to j do

\(\textnormal{D}\). for k= 1 to n-1 do; for i= 1 to n do; set j = i+k; for l= i to j do

答案

根据 OBST 的递归式 \(c_{ij} = \min_{i \leq l \leq j} \{ w_{ij} + c_{i,l-1} + c_{l+1,j} \}\)，为了迭代计算，必须按子问题规模从小到大填表。子问题的规模可通过键的数量衡量，令 \(k = j - i\) 表示子问题的长度参数，需从小规模到大规模遍历，而 i 遍历到 \(n\) 时，\(j = i+k\) 可能超出范围，故正确答案为 \(\textnormal{C}\)

In dynamic programming, we derive a recurrence relation for the solution to one subproblem in terms of solutions to other subproblems. To turn this relation into a bottom up dynamic programming algorithm, we need an order to fill in the solution cells in a table, such that all needed subproblems are solved before solving a subproblem. Among the following relations, which one is impossible to be computed.

\(\textnormal{A}\). \(A(i,j)=\min(A(i-1,j),A(i,j-1),A(i-1,j-1))\)

\(\textnormal{B}\). \(A(i,j)=F(A(\min\{i,j\}-1,\min\{i,j\}-1),A(\max\{i,j\}-1,\max\{i,j\}-1))\)

\(\textnormal{C}\). \(A(i,j)=F(A(i,j-1),A(i-1,j-1),A(i-1,j+1))\)

\(\textnormal{D}\). \(A(i,j)=F(A(i-2,j-2),A(i+2,j+2))\)

答案

\(\textnormal{D}\)

Floyd Shortest Path Algorithm

Floyd 算法思路

\(D^k[i][j] = \min\{D^{k-1}[i][j], D^{k-1}[i][k] + D^{k-1}[k][j]\}, k \geq 0\)

Why doesn't Floyd algorithm work if there are negative-cost cycles?

\(\textnormal{A}\). Because Floyd didn’t like negative numbers.

\(\textnormal{B}\). Because Floyd algorithm will terminate after finite steps, yet the shortest distance is negative infinity if there is a negative-cost cycle.

\(\textnormal{C}\). Because Floyd algorithm will fall into infinite loops.

\(\textnormal{D}\). Because a negative-cost cycle will result in a negative \(D[i][i]\), yet Floyd algorithm can only accept positive weights

答案

负权环是指一个环的总权重为负数（即绕这个环走一圈，路径长度会减少），若图中存在负权环，从某节点出发绕该环无限循环，能让路径长度无限减小（趋近于负无穷）。

弗洛伊德算法是确定性的动态规划过程，可以处理负权边（只要无负权环），其迭代次数有限（由节点数决定），不会陷入无限循环。但存在负权环时，最短距离实际是负无穷（可无限减小），算法无法捕捉这种情况，因此无法得到正确结果，故答案为 \(\textnormal{B}\)

Knapsack Problem

The time complexity of the dynamic programming algoritm to solve the knapsack problem ( 0-1 version) is polynomial, only if we round all profit values up to lie in smaller range.

答案

0-1 背包 DP 时间复杂度为 \(O(n·cap)\)，只要背包容量是物品数的多项式即为多项式时间，故答案为 \(\textnormal{F}\)

For the 0-1 knapsack problem, which of the following description is correct.

\(\textnormal{A}\). Greedy algorithm can be used to find the optimal solution

\(\textnormal{B}\). An efficient algorithm for finding polynomial time

\(\textnormal{C}\). The dynamic programming method introduced in the textbook can be used to solve any 0-1 knapsack problem

\(\textnormal{D}\). For the same knapsack and the same goods, the total value obtained by doing knapsack problem must be greater than or equal to 0-1 knapsack problem

答案

贪心算法只能求部分背包（物品可分割）的最优解，0-1背包物品不可分割，贪心选局部最优（如性价比最高）会错过全局最优，无法得到最优解，故 \(\textnormal{A}\) 错误

0-1 背包是 NP 完全问题，目前没有真多项式时间的高效精确算法（经典DP是伪多项式，依赖容量/价值数值大小，非仅物品个数），故 \(\textnormal{B}\) 错误

课本经典 DP 受背包容量 \(W\) 限制，若 \(W\) 极大时间复杂度会爆炸，无法实际求解，不能解决任何 0-1 背包，故 \(\textnormal{C}\) 错误

完全背包的选择范围更大（可多取高价值物品），因此总价值必然≥0-1背包的结果，故 \(\textnormal{D}\) 正确

综上所述，正确答案为 \(\textnormal{D}\)