什么样的问题可以用动态规划解决？解决动态规划问题的一般思考过程是什么样的？贪心、分治、回溯、动态规划这四种算法思想又有什么区别和联系？

1. “一个模型三个特征”理论讲解

1.1 一个模型，多阶段决策最优解模型

一般是用动态规划来解决最优问题。而解决问题的过程，需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。

1.2 三个特征

• 最优子结构

问题的最优解包含子问题的最优解。可以通过子问题的最优解，推导出问题的最优解。后面阶段的状态可以通过前面阶段的状态推导出来。

• 无后效性

第一层含义，在推导后面阶段的状态的时候，只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。

第二层含义，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。

• 重复子问题

不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。

2 .“一个模型三个特征”实例剖析

min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))

3.两种动态规划解题思路总结

1.状态转移表法
2.状态转移方程法

4. 四种算法思想比较分析

到今天为止，我们已经学习了四种算法思想，贪心、分治、回溯和动态规划。今天的内容主要讲些理论知识，我正好一块儿也分析一下这四种算法，看看它们之间有什么区别和联系。

如果我们将这四种算法思想分一下类，那贪心、回溯、动态规划可以归为一类，而分治单独可以作为一类，因为它跟其他三个都不大一样。为什么这么说呢？前三个算法解决问题的模型，都可以抽象成我们今天讲的那个多阶段决策最优解模型，而分治算法解决的问题尽管大部分也是最优解问题，但是，大部分都不能抽象成多阶段决策模型。

回溯算法是个“万金油”。基本上能用的动态规划、贪心解决的问题，我们都可以用回溯算法解决。回溯算法相当于穷举搜索。穷举所有的情况，然后对比得到最优解。不过，回溯算法的时间复杂度非常高，是指数级别的，只能用来解决小规模数据的问题。对于大规模数据的问题，用回溯算法解决的执行效率就很低了。

尽管动态规划比回溯算法高效，但是，并不是所有问题，都可以用动态规划来解决。能用动态规划解决的问题，需要满足三个特征，最优子结构、无后效性和重复子问题。在重复子问题这一点上，动态规划和分治算法的区分非常明显。分治算法要求分割成的子问题，不能有重复子问题，而动态规划正好相反，动态规划之所以高效，就是因为回溯算法实现中存在大量的重复子问题。

贪心算法实际上是动态规划算法的一种特殊情况。它解决问题起来更加高效，代码实现也更加简洁。不过，它可以解决的问题也更加有限。它能解决的问题需要满足三个条件，最优子结构、无后效性和贪心选择性（这里我们不怎么强调重复子问题）。

其中，最优子结构、无后效性跟动态规划中的无异。“贪心选择性”的意思是，通过局部最优的选择，能产生全局的最优选择。每一个阶段，我们都选择当前看起来最优的决策，所有阶段的决策完成之后，最终由这些局部最优解构成全局最优解。

最后

以上就是光亮帽子为你收集整理的41.讲动态规划理论：一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题1. “一个模型三个特征”理论讲解2 .“一个模型三个特征”实例剖析3.两种动态规划解题思路总结4. 四种算法思想比较分析的全部内容，希望文章能够帮你解决41.讲动态规划理论：一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题1. “一个模型三个特征”理论讲解2 .“一个模型三个特征”实例剖析3.两种动态规划解题思路总结4. 四种算法思想比较分析所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。