动态规划总结

动态规划的理解

1.png

2.png

3.png

4.png

2张5元和0张10元 后续也要求p1(arr,2,990),所以又重复计算，下面用一个数组记录已经求过的值


6.png

7.png
8.png

动态规划空间优化（滚动数组）

1.House Robber

house robber 1.png
house robber 2.png
house robber 3.png

house robber 5.png

house robber 4.png

2.Maximal Square

maximal square.png

局部最优和全局最优实现时间优化（global和local实现时间优化）

1.Maximum Subarray

Maximum Subarray.png

2.Maximum Product Subarray
也可以采用前n个乘积的思想

maximum product subarray.png

记忆化搜索

1.Longest Increasing Continuous Subsequence

记忆化搜索.png

记忆化搜索2.png

2.[LintCode]LongestIncreasing Continuous Subsequence II
当状态转移特别麻烦，不是顺序性，初始化状态不是很容易找到时可以用记忆化搜索，记忆化搜索可以用于任何地方。

I.博弈类-记忆化搜索

1.coins-in-a-line

coins in line.png

2.coins-in-a-line-ii

coins in line II.png
II.区间类-记忆化搜索

1.LintCode Coins in a line III

Coins in a line III.png

answer.png

2.Stone Game

stone game.png
stone game 2.png

stone game 1.png

3.攀爬字符串

scramble1.png
记忆化搜索.png
III.背包类

1.Backpack

backpack.png

把[1,24,5,6]数组尽量平分，其实就是两个背包容量为36/2 的问题
2.backpack ii

backpack II.png

3. k Sum

k Sum.png
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容