dynamic-programming - 动态规划递归或迭代

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) 等。这将是此问题的“动态规划”解决方案 - 使用线性时间和常数空间而不是指数时间(遍历三向树)和线性空间(用于调用堆栈)。