作业帮 > 数学 > 作业

【算法】请问动态规划和分治策略的差别是不是就在于对子问题的处理方式上?

来源:学生作业帮 编辑:拍题作业网作业帮 分类:数学作业 时间:2024/04/28 00:26:38
【算法】请问动态规划和分治策略的差别是不是就在于对子问题的处理方式上?
动态规划与分治策略都是将一个问题分解成为若干子问题,动态规划和分治相比,则有一个非常有用的性质,就是 动态规划中使用的子问题有大部分都是相同的(重叠子问题),这样我就可以通过记录每个子问题的答案使得 每个子问题 不被重复计算,从而 做到了 时间复杂度 上的 本质优化.
但是有些问题本身的子问题就不怎么重复,那样的话其实用不用动态规划都是一样的.