动态规划

Question

当阅读有关“算法导论”通过cormen动态编程，第15章：动态规划，我碰到这种说法

当开发一个动态规划算法，我们遵循来 四个步骤：

1. 表征最优解的结构。

2. 递归定义最优解的值。

3. 计算最优解的值，典型地在底向上的方式。

4. 从计算信息构建最佳解决方案。

步骤1-3形成动态编程解决一个问题的基础。如果我们需要 最优解的唯一的值，而不是溶液本身，那么我们 可以省略步骤4。当我们执行步骤4，步骤3，使我们可以很容易地构建一个最佳期间我们有时保持附加 信息解。

我不理解在步骤3和4

差分运算最优解

和

构建最佳解决方案的价值。

我期待通过阅读进一步了解这一点，但无法理解。 有人能通过举例帮助我理解这一点吗？

Answer 1

假设我们正在使用动态规划来制定出是否存在的一个子集[1,3,4,6,10]求和〜9

答案到步骤3是值，在此情况“真”。

答案到步骤4正在制定，总结于图9中，在这种情况下“3 + 6”的实际子集。

Answer 2

在动态编程中，我们大部分时间都会得到巨大的结果散列。然而，最初它只包含从第一个最小的最简单（底部）案例中获得的结果，并且通过使用这些初始结果并在其上进行计算，我们最终将合并到目标。此时，大部分时间散列中的最后一项是目标（步骤3完成）。然后我们将不得不处理它以获得所需的结果。

一个完美的例子可以找到总计达到目标的最小立方体数量。目标是500，我们应该得到[5,5,5,5]，或者如果目标是432，我们必须得到[6,6]。

所以我们可以在JS中执行这个任务如下：

function getMinimumCubes(tgt){ 
 
    var maxi = Math.floor(Math.fround(Math.pow(tgt,1/3))), 
 
     hash = {0:[[]]}, 
 
     cube = 0; 
 
    for (var i = 1; i <= maxi; i++){ 
 
    cube = i*i*i; 
 
    for (var j = 0; j <= tgt - cube; j++){ 
 
     hash[j+cube] = hash[j+cube] ? hash[j+cube].concat(hash[j].map(e => e.concat(i))) 
 
            : hash[j].map(e => e.concat(i)); 
 
    } 
 
    } 
 
    return hash[tgt].reduce((p,c) => p.length < c.length ? p:c); 
 
} 
 

 
var target = 432, 
 
    result = []; 
 
console.time("perf:"); 
 
result = getMinimumCubes(target); 
 
console.timeEnd("perf:"); 
 
console.log(result);

在此代码

所以，hash = {0:[[]]},是步骤1;最终准备hash[tgt]的嵌套循环实际上是第3步，返回阶段的.reduce()仿函数是第4步，因为它构成了散列的最后一项（hash[tgt]），通过筛选出最短结果给我们期望的结果所有结果中总计达到目标值。

对我而言，第2步有点毫无意义。不是因为提及递归，而是因为意义。除此之外，我从未在动态编程中使用过也没有看到过递归方法。最好用while或for循环来实现。