5.动态规划
5.1 什么是动态规划？
5.2 自底向上的动态规划：
5.3 自顶向下的动态规划
5.4 0-1背包问题：
5.5 完全背包问题
5.动态规划
5.1 什么是动态规划？
动态规划是⼀种把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划对于子问题重叠的情况特别有效，因为它将⼦问题的解保存在存储空间中，当需要某个子问题的解时，直接取值即可
5.2 自底向上的动态规划：
5.3 自顶向下的动态规划
5.4 0-1背包问题：
一个小偷面前有 n 个财宝，每个财宝有重量 w 和价值 v 两种属性，而他的背包只能携带一定重量的财宝（c），在已知所有财宝的重量和价值的情况下，如何选取财宝，可以最大限度的利用当前的背包容量，取得最大价值的财宝？（限定每种物品只有一个）
我们用 maxValue [i] [j] 来表示当前背包体积(j) 从(1,2,3, …i)件商品中选取最大价值的组合。
我们只考虑第 i 件商品，第 i 件商品只有两种情况，拿与不拿：
(1)若第 i 个物品在最优解中
我们直接最先将第 i 个物品其放入空背包中，此时背包剩余体积为 j-w，物品还有1,2,…,i-1，我们需要从其中继续找出最好的组合使得在背包体积为j-w且物品为1,2,…,i-1的情况下达到价值最高。由此可知：
maxValue [i] [j] = maxValue [ i-1 ] [ j-w ] + v
(2)若第 i 个物品不在最优解中
maxValue [i] [j] = maxValue [ i-1 ] [ j ]
得出结论
maxValue [i] [j] = max{ maxValue [ i-1 ] [ j-w ] + v，maxValue [ i-1 ] [ j ] }
5.5 完全背包问题：
此时，每种物品数量为无限。
(1)使用第 i 类物品
此时至少使用1个第 i 类物品。故而我们分析先用掉 1个第 i 类物品的情况： 此时背包剩余体积为 j-w
maxValue [i] [j] = maxValue [ i ] [ j-w ] + v （注意：前后都是 i，而不是出现 i-1，因为放入一个还可以继续放）
(2)不使用第 i 类物品
maxValue [i] [j] = maxValue [ i-1 ] [ j ]
