动态规划

动态规划（Dynamic Programming，DP）：将一个复杂的问题分解为若干个子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的解。
动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区别于贪心算法，贪心算法没有状态推导，而是从局部直接选最优的。

步骤

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. 初始化dp数组
4. 确定遍历顺序
5. 举例推导dp数组

适用条件

动态规划适用于有重叠子问题和最优子结构性质的问题。

重叠子问题

重叠子问题：在使用分治算法时，相同的子问题会被重复计算多次。

最优子结构

最优子结构：一个问题的最优解包含其子问题的最优解。

0-1背包

问题描述

有N件物品和一个最多能承受重量为W的背包，第i件物品的重量是weight[i]，价值是value[i]。每件物品只能用一次，求解将哪些物品装入背包可使价值总和最大？

完全背包

问题描述

有N件物品和一个最多能背重量为W的背包，第i件物品的重量是weight[i]，价值是value[i]。每件物品无限个，求解将哪些物品装入背包可使价值总和最大？