更新时间:2022-05-24 22:17:38
动态编程?给定一个数组 A[0..n]
,让 M(i)
成为使用索引为 0..i
的元素的最优解.然后M(-1) = 0
(在循环中使用),M(0) = A[0]
,M(i) = max(M(i - 1), M(i - 2) + A[i]) 对于 i = 1, ..., n
.M(n)
就是我们想要的解决方案.这是 O(n).您可以使用另一个数组来存储为每个子问题做出的选择,从而恢复实际选择的元素.
Dynamic programming? Given an array A[0..n]
, let M(i)
be the optimal solution using the elements with indices 0..i
. Then M(-1) = 0
(used in the recurrence), M(0) = A[0]
, and M(i) = max(M(i - 1), M(i - 2) + A[i]) for i = 1, ..., n
. M(n)
is the solution we want. This is O(n). You can use another array to store which choice is made for each subproblem, and so recover the actual elements chosen.