动态规划

一：什么是动态规划？

动态规划是运筹学的一个分支，是求解策略过程最优化的过程。

动态规划并不是一种算法，而是一种思想，或者说策略。

动态规划可以达到最优的 O(n²) 复杂度。

二：基本思想

将大问题分解为一个一个的小问题，将小问题逐个击破，大问题就解决了。

三：实例

假设有一个可容纳4kg商品的购物篮，现有四件商品可供选择，如何装购物篮的价值最高？

枚举法

动态规划

启示

• 动态规划可以帮助我们在给定约束条件下找到最优解。在上面的问题中，你必须在购物篮容量给定的情况下，拿到价值最高的商品。
• 在问题可分解为彼此独立且离散的子问题时，就可以采用动态规划来解决。
• 每种动态规划解决方案都涉及网格
• 表格中的值通常就是要优化的值。在上面的问题中，表格的值为商品的价值。
• 每个表格都是一个子问题，因此你应该考虑如何将问题分成子问题，这样有助于找出网格的坐标轴。

四：动态规划的应用

• 最短路径（弗洛伊德算法）
• 库存管理
• 资源分配
• 设备更新
• 排序
• 装载

五：策略

• 没有放之四海皆准的公式，有的只是解决问题的方式。
• 动态规划，并非无所不能，具体问题具体分析，选择合适的策略，才是最好的。
• 自底而上的考虑问题，从最简单的情况出发，将大问题拆解为小问题，解决小问题，从而化解大问题。