内容：

• 动态规划，它将问题分成小问题，并先着手解决这些小问题
• 学习如何设计问题的动态规划解决方案

9.1 背包问题

　　如何让背包内装的商品价值最高？

如果尝试所有的可能性，运行时间为O(2ⁿ)。

9.2 背包问题FAQ

　　9.2.7处理相互依赖的情况

　　　　动态规划仅当每个子问题是离散的情况下才管用。即子问题之间不能有依赖。

　　9.2.8根据动态规划的设计，最多只需合并两个自背包，即根本不涉及两个以上的子背包，但子背包可能又含有子背包。

　　9.2.9最优解可能导致背包没装满9

9.3最长公共子串

• 动态规划可在给定约束条件下找到最优解
• 在问题可分解为彼此独立且离散的子问题时，就可使用动态规划来解决

9.4小结

• 需要给定约束条件下右下某种指标时，动态规划很有用
• 问题可分为离散子问题时，可使用动态规划来解决
• 每种动态规划方案都涉及网格
• 单元格中的值通常就是你要优化的值
• 每个单元格都是一个子问题，因此需要考虑如何将问题分为子问题
• 没有房子四海皆准的计算动态规划解决方案的公式

动态规划C语言