动态编程递归或迭代

Question

我正在阅读动态编程,我对它很陌生.我想知道动态编程是否可以以"迭代"和"递归"方式应用,或者仅将其中一种方式应用于它是一种好习惯.任何好的例子/链接都会有所帮助.

Answer 1

动态编程(在许多情况下)可以看作是反向实现的递归解决方案.

通常,在递归中,您将x(n+1) = f(x(n))使用某些停止条件n=0(或某个其他值)进行计算.

在许多情况下,该函数f是一些最小/最大函数,但它不一定是.此外,该函数不必采用单个变量.

动态规划将通过计算解决这一问题f(0),那么f(1),再f(2)等等.

对于多个变量,通常会有一些自然顺序来计算函数.

动态编程可以解决的一个例子:你有3个高尔夫球杆.每个高尔夫球杆可以向前发送高尔夫球x个单位(例如,24,37和54个单位).问题是:你能打到距离正好200个单位的洞吗？如果可以的话,你需要的最小射击次数是多少.

递归解决方案将是这样的:

shots(200) = min(shots(200-24),shots(200-37),shots(200-54))

这将允许一个简单的实现,其中shot(n)如果n为0,则函数返回0,如果n小于0,则返回一些大数,否则返回上面的表达式.

但是,对于较大的n值,您将从上面表达式的不同分支中反复尝试相同的值.在这种情况下,它只是为了更好地从0开始,计算shots(0),shots(1),shots(2)等,这将是"动态规划"解决了这个问题-使用线性时间和恒定的空间,而不是指数时间(运行3路树)和线性空间充其量(对于调用堆栈).

Answer 2

是的,DP可以应用于两者.

从这里开始:http://en.wikipedia.org/wiki/Dynamic_programming

然后你有动态编程:从新手到高级和动态编程教程

对于第一个教程,您将找到TopCoder.com练习问题的链接(这些问题中的每一个都有一个编辑解释解决方案背后的想法.