动态规划法
考的最多
动态规划法(Dynamic Programming):在求解问题中，对于每一步决策，列出各种可能的局部解，通过决策生存那些有可能达到最优的局部解，抛弃其它局部解，以每一步都是最优解来保证全局是最优解。
本质也是将复杂的问题划分成一个个子问题，与分治法差别的是分治法中的每个子问题都是相同的，而动态规划法中的每个子问题间不是相互独立的，而且不全都相同。
此算法会将大量精力放在前期构造表格上面，其会对每一步，列出各种可能的答案，这些答案会存储起来，最终要得出某个结果时，是通过查询这张表来得到的。动态规法不但每一步最优，全局也最优。
总结：动态规划一定是具备了以下三个特点：
- 把原来的问题分解成了几个相似的子问题。(夸大“相似子问题”)
- 全部的子问题都只须要解决一次。（夸大“只解决一次”）
- 储存子问题的解。（夸大“储存”）
例子
我们继续拿斐波那契数列来打比方。斐波那数列1 1 2 3 5 8 13 21…前两数的和是后一个数的值
左下图是使用递归来求解的写法，显然，这是一个非常低效的方法，因为其中有大量的重复计算。而且不满足动态规划的第二个特点：“全部的子问题都只须要解决一次“，这个问题很好解决，我们只须要利用动态规划的第三个特点：”储存子问题的解“就可以了。好比，如果已经计算过Fibonacci(3),那么把结果储存起来，其他地方遇到须要求Fibonacci(3)的时候，就不须要计算，直接调用结果就行。这样做之后，蓝色表现须要举行计算的，白色表现可以直接从存储中取得结果的：
在这里插入图片描述
递归求法
- long long Fib(int n)
- {
- if (n==1 || n==2)
- return 1;
- return Fib(n - 1) + Fib(n - 2);
- }
贪心法
贪心法：总是做出在当前来说是最好的选择，而并不从整体上加以考虑，它所做的每步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。由于它不比为了寻找最优解而穷尽全部可能解，因此其耗费时间少，一样平常可以快速得到满足的解，但得不到最优解。
局部贪心，只针对档前的步骤取最优，而非整体考虑。
判断此类算法，就看算法是否是每一步都取最优，而且整体题意没有透暴露最终结果是最优的。
例子
假设你身上带了足够的1、5、10、20、50、100元面值的钞票。如今您的目的是凑出某个金额w,而且须要用到尽量少的钞票。依据生活履历，我们可以接纳这样的计谋：能用100的就尽量用100的，否则尽量用50的…依次类推。在这种计谋下，666=6×100+1×50+1×10+1×5+1×1，共使用了10张钞票。
这种计谋称为“贪心”：假设我们面临的局面是“须要凑出w”,贪心计谋会尽快让w变得更小。能让w少100就尽量让它少100，这样我们接下来面临的局面就是凑出w-100。长期的生活履历表明，贪心计谋是准确的。
但是，如果我们换一组钞票的面值，贪心计谋就也许不成立了。如果一个奇葩国家的钞票面额分别是1、5、11，那么我们在凑出15的时候，贪心计谋会出错：15=1×11+4×1（贪心计谋使用了5张钞票)，15=3×5（准确的计谋，只用3张钞票）
为什么会这样呢？贪心计谋错在了那里？
刚刚已经说过，贪心计谋的纲领是：“尽量使接下来面临的w更小”。这样，贪心计谋在w=15的局面时，会优先使用11来把w降到4；但是在这个问题中，凑出4的代价是很高的，必须使用4×1。如果使用了5，w会降为10，虽然没有4那么小，但是凑出10只须要两张5元。
在这里我们发现，贪心是一种只考虑眼前情况的计谋。
DP解决方法
如果直接暴力枚举凑出的方案，明显复杂度过高。太多种方法可以凑出w了，枚举它们的时间是不可承受的。我们如今来实验找一下性质。
重新分析刚网刚的例子。w=15时，我们如果取11，接下来就面临w=4的情况；如果取5，则接下来面临w=10的情况。我们发现这些问题都有相同的形式："给定w,凑出w所用的最少钞票是多少张？”接下来，我们用f(n)来表现“"凑出n所需的最少钞票数量”。
那么，如果我们取了11，最后的代价（用掉的钞票总数）是多少呢？
明显cost=f(4)+1=4+1=5,它的意义是：利用11来凑出15，付出的代价等于f(4)加上自己这一张钞票。如今我们暂时不管f(4)怎么求出来。
依次类推，立即可以知道：如果我们用5来凑出15，cost就是f(10)+1=2+1=3
那么，如今w=15的时候，我们该取那种钞票呢？固然是各种方案中，c0st值最低的那一个！
- 取11：cost=f(4)+1=4+1=5
- 取5：cost=f10)+1=2+1=3
- 取1：cost=f(14)+1=4+1=5
显而易见，cost值最低的是取5的方案。我们通过上面三个式子，做出了准确的决策！
这给了我们一个至关重要的启示一一f(n)只与f(n-1),f(n-5),f(n-11)相关；更确切地说：
f(n)=min{f(n-1),f(m-5),f(n-11)}+1
这就是DP(动态规划，dynamic programming)
将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
