algorithm - 贪心算法是否可能也是动态规划算法？

Question

算法是否可能greedy也是dynamic programming算法？

我上了一堂Analysis of Algorithms课，但我仍然不确定这两个概念。

我理解贪婪方法使用当前最优解来找到全局最优解，并且 DP 算法重用重叠的子结果。

我相信答案是“是”，但我找不到一个既是贪婪算法又是 DP 算法的好例子。

有人可以给我一个例子吗？

如果上述问题的答案是“否”，那么有人可以向我解释为什么吗？

标签： algorithmdynamic-programminggreedy

Answer 1

从贝尔曼方程来看：

如果在最小化过程中我们可以将 f 部分（当前时期）与 J 部分（与之前时期的最优）分开，那么这恰好对应于贪婪方法。一个简单的例子是当优化函数是每个时期的成本总和时，

J(u1,u2,...)= sum(f_i(u_i)).