1. 动态规划

背包问题：背包可以容纳的重量是4磅，吉他为1磅，价值1500元；音响为4磅，价值3000元；笔记本电脑为3磅，价值为2000元。如何在背包中放入价值最大的物品？

背包问题中如果采用穷举法，那么时间复杂度为$O(2^n)$。因此引出动态规划的方法。

动态规划：先解决子问题，在逐步解决大问题。





使用的公式为：

• 再增加一个商品手机，重量为1磅，价值为2000元。此时计算只需要增加一行，为不需要将之前的计算重新开始。
  
• 不断往下计算时，只需要考虑上一行的数值与当前行的数值比较，采用最大数值来填充。
• 如果放入量化单位更小的物体，则需要将考虑的粒度更细，因此必须重新调整表格。

2. 案例

2.1 旅游行程最优化

动态规划使用范围：但仅当每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用。当涉及两个以上的背包时，只需要调整细粒度来进行填装即可。并且最优解可能导致背包 没有装满。

2.2 最长公共子串

问题描述：寻找两个字符中相同的字母最多的数量。