演算法›Ch3 動態規劃
第 6 題/共 40 題
◀ AL 6/40
6. Dynamic Programming、分段最佳化
#AL-03-006難Dynamic Programming分段最佳化

Consider a sequence of numbers (v1,…,vn)(v_1, \ldots, v_n). Now we remove kk numbers from the sequence so that we have k+1k+1 non-empty segments of numbers. For example, consider (2,3,8,1,4)(2,3,8,1,4). If we remove 8 then we have two segments (2,3)(2,3) and (1,4)(1,4).

Now we want to minimize the maximum sum of numbers of a segment. Let m(1,n,k)m(1,n,k) be the answer, then what is the correct recursion for mm when 1≤i<j≤n1 \le i < j \le n and 0<k≤(j−i)/20 < k \le (j-i)/2?

📄 台大113
跳轉到第題
▤完整推導請見《WH 資工筆記 · 演算法》Ch3 動態規劃
本章題號 · 1–20 / 40