贪心算法有没有可能也是动态规划算法？
Is it possible that a greedy algorithm is also a dynamic programming algorithm?
有没有可能 greedy 算法也是 dynamic programming 算法？
我考了 Analysis of Algorithms class 但是，我仍然不确定这两个概念。
我理解贪心法是利用当前最优解寻找全局最优解，DP算法重用重叠的子结果。
我相信答案是"YES"但是我找不到一个既贪婪又DP算法的好例子
有人能给我举个例子吗？
如果上述问题的答案是 "NO" 那么有人可以向我解释为什么吗？
这是我的理解
贪心算法和动态算法是两个不同的东西。贪心算法总是做出那个时刻看起来最好的选择。无论接下来会发生什么，它都会在新选项弹出后立即做出选择。
动态算法是结合子程序的解得到最终解。它根据子程序的结果做出决定，并且通常在存在影响最终解决方案的变量时起作用。所以，这是两种思维方式。
动态算法总是在贪心算法可以解决的问题上起作用，但是动态算法的时间成本和space成本都比贪心算法高很多。贪心算法大多不能解决DP问题
所以答案是否定的
在优化算法中，贪心法和动态规划法基本上是对立的。贪婪的方法是选择局部最优的选项，而动态规划的全部目的是有效地评估整个选项范围。
但这并不意味着您不能拥有同时利用这两种策略的算法。例如，A* 寻路算法就是这样做的，它既是贪心算法又是动态规划算法。它使用贪婪方法优化最佳情况，并使用动态规划方法优化最坏情况。
从贝尔曼方程看：
如果在最小化中我们可以将 f 部分（当前周期）与 J 部分（先前周期的最优值）分开，那么这恰好对应于贪心法。一个简单的例子是当优化函数是每个时期成本的总和时，
J(u1,u2,...)= sum(f_i(u_i)).
有没有可能 greedy 算法也是 dynamic programming 算法？
我考了 Analysis of Algorithms class 但是，我仍然不确定这两个概念。
我理解贪心法是利用当前最优解寻找全局最优解，DP算法重用重叠的子结果。
我相信答案是"YES"但是我找不到一个既贪婪又DP算法的好例子
有人能给我举个例子吗？
如果上述问题的答案是 "NO" 那么有人可以向我解释为什么吗？
这是我的理解
贪心算法和动态算法是两个不同的东西。贪心算法总是做出那个时刻看起来最好的选择。无论接下来会发生什么，它都会在新选项弹出后立即做出选择。 动态算法是结合子程序的解得到最终解。它根据子程序的结果做出决定，并且通常在存在影响最终解决方案的变量时起作用。所以，这是两种思维方式。
动态算法总是在贪心算法可以解决的问题上起作用，但是动态算法的时间成本和space成本都比贪心算法高很多。贪心算法大多不能解决DP问题
所以答案是否定的
在优化算法中，贪心法和动态规划法基本上是对立的。贪婪的方法是选择局部最优的选项，而动态规划的全部目的是有效地评估整个选项范围。
但这并不意味着您不能拥有同时利用这两种策略的算法。例如，A* 寻路算法就是这样做的，它既是贪心算法又是动态规划算法。它使用贪婪方法优化最佳情况，并使用动态规划方法优化最坏情况。
从贝尔曼方程看：
如果在最小化中我们可以将 f 部分（当前周期）与 J 部分（先前周期的最优值）分开，那么这恰好对应于贪心法。一个简单的例子是当优化函数是每个时期成本的总和时，
J(u1,u2,...)= sum(f_i(u_i)).