递推、搜索、贪心和动态规划的区别

递推:每个阶段只有一个状态;

搜索:每个阶段的最优状态是由之前所有阶段的状态的组合得到的;

贪心:每个阶段的最优状态都是由上一个阶段的最优状态得到的;

动态规划:每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到(最优子结构),而不管之前这个状态是如何得到的(无后效性)。

分享到