关于动态规划与贪心算法的一点理解

时间:2022-03-01 23:53:59

关于动态规划算法的应用,是有迭代的,而且不能有后效性,即后面的状态不能影响到当前。

例子:关于应用动态规划算法的一个例子,就是何时股票问题利润最大化问题:

每走一步都记录出现的最小值,并检查下利润否大于当前的最优值

关于贪心算法的应用,当单个子问题就可以决定父问题,可以用贪心法

例子:最长无重复子串问题

假设子串里含有重复字符,则父串一定含有重复字符,单个子问题就可以决定父问题,因此可以用贪心法。跟动规不同,动规里,单个子问题只能影响父问题,不足以决定父问题。