《算法图解》——第九章 动态规划
第九章 动态规划
1动态规划——背包问题
公式：
练习
9.1 假设你还可偷另外一件商品——MP3播放器，它重1磅，价值1000美元。你要偷吗？
要。在这种情况下，你可偷来MP3播放器和iPhone和吉他，总价值为4500美元
行的排列顺序发生变化时结果如何？答案没有变化。也就是说，各行的排列顺序无关紧要。
可以逐行而不是逐列填充网格吗？就这个问题而言，这没有任何影响，但对于其他问题，可能有影响。
增加一件更小的商品将如何呢？你需要考虑的粒度更细，因此必须调整网格。
可以偷走商品的一部分吗？答案是没法处理。使用动态规划时，要么考虑拿走整件商品，要么考虑不拿，而没法判断该不该拿走商品的一部分。但是贪婪算法可以轻松处理！
2旅行行程最大化
根据清单画动态规划网格：
如何处理相互依赖的情况？
动态规划功能强大，它能够解决子问题并使用这些答案来解决大问题。但仅当每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用。
计算最终的解时会涉及两个以上的子背包吗？
为获得前述背包问题的最优解，可能需要偷两件以上的商品。但根据动态规划算法的设计，最多只需合并两个子背包，即根本不会涉及两个以上的子背包。不过这些子背包可能又包含子背包。
最优解可能导致背包没装满吗？of course
练习
9.2 假设你要去野营。你有一个容量为6磅的背包，需要决定该携带下面的哪些东西。其中每样东西都有相应的价值，价值越大意味着越重要：
水（重3磅，价值10）；
书（重1磅，价值3）
食物（重2磅，价值9）；
夹克（重2磅，价值5）；
相机（重1磅，价值6）。
请问携带哪些东西时价值最高？用动态规划做呗，水，食物，相机
3最长公共子串
动态规划的启示：
①动态规划可帮助你在给定约束条件下找到最优解。
②在问题可分解为彼此独立且离散的子问题时，就可使用动态规划来解决。
③每种动态规划解决方案都涉及网格。
④单元格中的值通常就是你要优化的值。
⑤每个单元格都是一个子问题，因此你应考虑如何将问题分成子问题，这有助于你找出网格的坐标轴。
举个