算法简介：动态规划
动态规划
- 1. 动态规划
- 2. 案例
- 2.1 旅游行程最优化
- 2.2 最长公共子串
1. 动态规划
背包问题：背包可以容纳的重量是4磅，吉他为1磅，价值1500元；音响为4磅，价值3000元；笔记本电脑为3磅，价值为2000元。如何在背包中放入价值最大的物品？
背包问题中如果采用穷举法，那么时间复杂度为 O ( 2 n ) O(2^n) O(2n)。因此引出动态规划的方法。
动态规划：先解决子问题，在逐步解决大问题。
使用的公式为：
- 再增加一个商品手机，重量为1磅，价值为2000元。此时计算只需要增加一行，为不需要将之前的计算重新开始。
- 不断往下计算时，只需要考虑上一行的数值与当前行的数值比较，采用最大数值来填充。
- 如果放入量化单位更小的物体，则需要将考虑的粒度更细，因此必须重新调整表格。
2. 案例
2.1 旅游行程最优化
动态规划使用范围：但仅当每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用。当涉及两个以上的背包时，只需要调整细粒度来进行填装即可。并且最优解可能导致背包 没有装满。
2.2 最长公共子串
问题描述：寻找两个字符中相同的字母最多的数量。
