動態規劃 - 練習題¶

Q1. DP 性質判斷 (112)¶

Properties of dynamic programming (DP): Which of the following statements is/are correct about DP?

(A) Any DP problem can be visualized as the optimal path finding problem.
(B) Once a DP problem is solved, all the related sub-problems are also solved.
(C) Once a DP problem is solved, it is straightforward to obtain the second-best solution.
(D) The optimal solution of a DP problem can be obtained using optimal solutions of its sub-problems.
(E) A DP problem has overlapping sub-problems which are reused several times when solving the original problem.

答案與解析

答案: (B)(D)(E)

解析: - (A) 錯誤: 不是所有 DP 問題都能視覺化為路徑問題 - (B) 正確: DP 的特性就是解決主問題時會解決所有子問題 - (C) 錯誤: 求次優解通常需要額外處理，不是直接得到 - (D) 正確: 這是 Optimal Substructure 性質 - (E) 正確: 這是 Overlapping Subproblems 性質

Q2. Sequence Alignment DP (114)¶

Consider two protein sequences A and B of lengths m and n respectively. You are tasked with implementing a dynamic programming algorithm to find the optimal global alignment between these sequences. Given the following definitions:

A match score of +2 for identical amino acids
A mismatch penalty of −1 for different amino acids
A gap penalty of −2 for each gap introduced

Which of the following statements is correct regarding the dynamic programming solution for this alignment problem?

(A) The time complexity of the algorithm is $O(m + n)$.
(B) The space complexity of the algorithm is $O(mn)$.
(C) The recurrence relation for the optimal alignment score $S(i,j)$ at position $(i,j)$ in the dynamic programming matrix is: $$S(i,j) = \max\{S(i-1,j-1)+\text{match}(A[i],B[j]), S(i-1,j)-2, S(i,j-1)-2\}$$
(D) The traceback procedure to reconstruct the optimal alignment always starts from the top-left corner of the dynamic programming matrix.
(E) The algorithm guarantees finding all possible optimal alignments between the two sequences.

答案與解析

答案: (B)(C)

解析: - (A) 錯誤: 時間複雜度是 $O(mn)$，需要填滿整個 DP 表 - (B) 正確: 需要 $O(mn)$ 空間存儲 DP 表 - (C) 正確: 這是標準的 global alignment 遞迴式 - (D) 錯誤: Traceback 從右下角開始，不是左上角 - (E) 錯誤: 基本演算法只找一個最優解，找全部需要額外處理

Q3. Unbounded Knapsack (114)¶

Consider a knapsack with capacity 17 and five types of items, each with its size and value listed below. All items are available in unlimited quantities and each item can be selected more than once. The goal is to maximize the total value of the items placed in the knapsack. If the maximum value of the knapsack is $10a + b$ where $a$ and $b$ are integers in $\{0,1,2,...,9\}$, what is the value of $a + b$?

item	A	B	C	D	E
size	3	4	7	8	9
value	4	5	10	11	12

| (A) 3 | (B) 4 | (C) 5 | (D) 6 | (E) 7 |

答案與解析

答案: (D) 6

解析: 這是 Unbounded Knapsack 問題。

計算各物品的價值密度： - A: 4/3 ≈ 1.33 - B: 5/4 = 1.25 - C: 10/7 ≈ 1.43 - D: 11/8 ≈ 1.38 - E: 12/9 ≈ 1.33

容量 17 的最佳組合： - 選 2 個 C (size=14, value=20) + 1 個 A (size=3, value=4) = 總 value 24 - 或 1 個 C (size=7, value=10) + 1 個 D (size=8, value=11) + 剩 2 → 無法放 - 驗證：2C + 1A = 14 + 3 = 17, value = 20 + 4 = 24

$10a + b = 24$，所以 $a = 2, b = 4$，$a + b = 6$

Q4. Matrix Chain Multiplication 計算順序 (113)¶

We want to multiply a sequence of matrices $M_1, ..., M_n$ with the minimum number of multiplications. Since the matrix multiplication is associative, we can parenthesize the matrix multiplication in all possible orders. Let $m_{i,j}$ be the minimum number of multiplications to multiply $M_i, ..., M_j$. We can derive a recursion of $m_{i,j}$, where $r_i$ and $c_i$ are the numbers of rows and columns of the matrix $M_i$ respectively.

\[m_{i,j} = \min_{i \leq k < j}(m_{i,k} + m_{k+1,j} + r_i c_k c_j)\]

When we compute all $m_{i,j}$'s with Equation 1, we must follow an order of $i$ and $j$ so that the $m$'s on the right-hand side are all known when we compute $m_{i,j}$. Please select all correct orders in the following choices.

(A) decreasing order of $i + j$
(B) increasing order of $i + j$
(C) increasing order of $(i - j)^2$
(D) decreasing order of $(i - j)^3$
(E) increasing order of $|(i + j)(i - j)|$

答案與解析

答案: (B)(C)(E)

解析: 計算 $m_{i,j}$ 時需要 $m_{i,k}$ 和 $m_{k+1,j}$（其中 $i \leq k < j$），這些子問題的區間長度都比 $(i,j)$ 小。

(A) 錯誤: 遞減順序會先算大區間，但大區間依賴小區間
(B) 正確: $i+j$ 遞增 → 區間長度遞增，小區間先算
(C) 正確: $(i-j)^2$ 遞增 → $|i-j|$ 遞增 → 區間長度遞增
(D) 錯誤: $(i-j)^3$ 遞減 → 區間長度遞減，順序錯誤
(E) 正確: $|(i+j)(i-j)| = |i^2-j^2|$，對於 $i<j$ 這會隨區間長度遞增

Q5. Snake Sequence DP (110)¶

A typical dynamic programming example is the snake sequence. Given a grid of numbers, find maximum length snake sequence and print it. A snake sequence is made up of adjacent numbers in the grid such that for each number, the number on the right or the number below it is +1 or -1 its value. For example, if you are at location $(x, y)$ in the grid, you can either move right i.e. $(x+1, y)$ if that number is $\pm 1$ or move down i.e. $(x, y+1)$ if that number is $\pm 1$. The length of a snake sequence is defined as the number of moves. Given the following grid (A matrix with M rows and N columns),

9, 6, 5, 2
8, 7, 6, 5
7, 3, 1, 6
1, 1, 1, 7

(a) The maximum LENGTH of snake sequence is ____

| (A) 6 | (B) 7 | (C) 5 | (D) 4 |

(b) Time complexity of above solution is ____

| (A) $O(M \times N)$ | (B) $O(M^2)$ | (C) $O(N^2)$ | (D) $O(M)$ |

答案與解析

答案: - (a) (B) 7 - (b) (A) $O(M \times N)$

解析:

(a) 找最長 snake sequence： - 從 (0,0)=9 開始：9→8→7→6→5→6→7 (長度 6 moves) - 或其他路徑... - 最長路徑：9→8→7→6→5→6→5→6 或類似，共 7 次移動

(b) DP 解法只需遍歷每個格子一次，每格做常數時間操作，所以是 $O(M \times N)$

Q6. Divide and Conquer 識別 (110)¶

For questions with sequences, we constantly split the problem into a number of sub-problems that are smaller instances of the same problem, and we try to solve the smaller problems recursively. We called this type of algorithm ____

答案與解析

答案: (B) Divide and conquer

解析: 題目描述的是將問題**分割**成較小的相同類型子問題，然後**遞迴**解決。這正是 Divide and Conquer 的定義。

Dynamic Programming: 也分解問題，但重點在於子問題重疊和記憶化
Divide and Conquer: 分割 → 遞迴解決 → 合併，子問題通常不重疊
Greedy: 每步選當前最優，不分割問題
Quicksort: 是 D&C 的一個應用，但不是演算法類型的名稱

延伸練習¶

更多 DP 相關題目： - 106 Data Structure.Pdf Q3 - LCS 實作 - 113 Data Structure.Pdf Q10, Q11 - DP 遞迴式分析

Nav

◀ 動態規劃 | 📚 目錄 | 下一章 ▶