algorithm - cormen 书中的动态规划

Question

在阅读 cormen 的“算法导论”第 15 章:动态规划中的动态规划时，我遇到了这个语句

When developing a dynamic-programming algorithm, we follow a sequence offour steps:

1. Characterize the structure of an optimal solution.

2. Recursively define the value of an optimal solution.

3. Compute the value of an optimal solution, typically in a bottom-up fashion.

4. Construct an optimal solution from computed information.

Steps 1–3 form the basis of a dynamic-programming solution to a problem. If weneed only the value of an optimal solution, and not the solution itself, then wecan omit step 4. When we do perform step 4, we sometimes maintain additionalinformation during step 3 so that we can easily construct an optimal solution.

我不明白第 3 步和第 4 步的区别。

计算最优解的值

和

构造最优解。

我本希望通过进一步阅读来理解这一点，但未能理解。有人可以举个例子帮助我理解这一点吗？

Answer 1

假设我们正在使用动态规划来计算 [1,3,4,6,10] 中是否存在总和为 9 的子集。

第 3 步的答案是值，在本例中为“TRUE”。

第 4 步的答案是计算总和为 9 的实际子集，在本例中为“3+6”。