动态规划的新手解释是什么？

Question

我正在尝试学习动态规划 (DP) 的基础知识，并浏览了一些我可以获得的在线资源，例如...

What is dynamic programming?
Good examples, articles, books for understanding dynamic programming
Tutorial for Dynamic Programming
Dynamic Programming – From Novice to Advanced --（我没法理解（即如何使用DP解决问题））

直到现在我才明白

A dynamic problem is almost same that of recursion with just a difference (which gives it the power it is know for)

i.e. storing the value or solution we got and using it again to find next solution

例如：

根据codechef的解释

问题：最小步数到一个

问题陈述：对于正整数，您可以执行以下 3 个步骤中的任何一个。

从中减去1。 ( n = n - 1 )
如果它能被 2 整除，则除以 2。（如果 n % 2 == 0，则 n = n / 2）
如果它能被 3 整除，则除以 3。（如果 n % 3 == 0，则 n = n / 3）

现在的问题是，给定一个正整数n，求n到1的最少步数

例如：

对于 n = 1 ，输出：0
对于 n = 4 ，输出：2 ( 4 /2 = 2 /2 = 1 )
对于 n = 7 ，输出：3 ( 7 -1 = 6 /3 = 2 /2 = 1 )

内部备忘录[n+1]; // 我们将把元素初始化为 -1（-1 意味着，还没有解决）

上述问题的自上而下方法

int getMinSteps ( int n ) {
    if ( n == 1 )  return 0;
    if( memo[n] != -1 ) return memo[n];
    int r = 1 + getMinSteps( n - 1 );
    if( n%2 == 0 )   r  =  min( r , 1 + getMinSteps( n / 2 ) );
    if( n%3 == 0 )   r  =  min( r , 1 + getMinSteps( n / 3 ) );
    memo[n] = r ;  // save the result. If you forget this step, then its same as plain recursion.
    return r;
}

我对 dp 的理解是否正确，或者任何人都可以用更好更简单的方式解释它，以便我可以学习它并可以使用动态规划解决问题。

Answer 1

来自维基百科的 Fibonacci sequence 示例提供了一个很好的例子。

动态规划是一种优化技术，它假设问题满足 principle of optimality，将潜在的指数递归解转换为多项式时间解。基本上意味着您可以从最佳子问题构建最佳解决方案。 tractable 动态规划问题的另一个重要特征是它们 overlapping。如果将这些问题分解为重复的子问题，则可以重复使用相同的解决方案来解决这些子问题。具有最优子结构属性和重叠子问题的问题，动态规划是一种潜在的有效解决方法。

在示例中，您可以看到斐波那契数列的递归版本会在树状结构中增长，表明指数爆炸。

function fib(n)
       if n <=1 return n
       return fib(n − 1) + fib(n − 2)

所以 fib(5) 你得到：

fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))

以此类推时尚之树

动态规划让我们可以在多项式时间内使用最优子问题逐步构建解决方案。这通常通过某种形式的记录保存来完成，例如 table。请注意，子问题有重复的实例，即 fib(2) 计算一次就足够了。

同样来自维基百科，动态规划解决方案

function fib(n)
   if n = 0
       return 0
   else
       var previousFib := 0, currentFib := 1
       repeat n − 1 times // loop is skipped if n = 1
           var newFib := previousFib + currentFib
           previousFib := currentFib
           currentFib  := newFib
   return currentFib

此处的解决方案是根据初始设置的 previousFib 和 currentFib 构建的。 newFib 是根据此循环中前面的步骤计算得出的。 previousFib 和 currentFib 代表我们对之前子问题的记录。

结果是一个多项式时间解（在本例中为 O(n)），其递归公式为指数形式（在本例中为 O(2^n)）。

Answer 2

有精彩回答How should I explain dynamic programming to a 4-year-old? 只是在这里引用相同的内容：

Writes down "1+1+1+1+1+1+1+1 =" on a sheet of paper

"What's that equal to?"

counting "Eight!"

writes down another "1+" on the left

"What about that?" quickly "Nine!"

"How'd you know it was nine so fast?"

"You just added one more"

"So you didn't need to recount because you remembered there were eight! Dynamic Programming is just a fancy way to say 'remembering stuff to save time later'"

动态规划的新手解释是什么？

What can be a newbie explanation for a dynamic programming?

dynamic-programming