算法知识点
动态规划是一种多阶段决策最优解模型，一般用来求最值问题，多数情况下它可以采用自下而上的递推方式来得出每个子问题的最优解（即最优子结构），进而自然而然地得出依赖子问题的原问题的最优解。
三个特性：
- 多阶段决策，意味着问题可以分解成子问题，子子问题，。。。，也就是说问题可以拆分成多个子问题进行求解
- 最优子结构，在自下而上的递推过程中，我们求得的每个子问题一定是全局最优解，既然它分解的子问题是全局最优解，那么依赖于它们解的原问题自然也是全局最优解。
- 自下而上，怎样才能自下而上的求出每个子问题的最优解呢，可以肯定子问题之间是有一定联系的，即迭代递推公式，也叫「状态转移方程」，要定义好这个状态转移方程， 我们就需要定义好每个子问题的状态（DP 状态），那为啥要自下而上地求解呢，因为如果采用像递归这样自顶向下的求解方式，子问题之间可能存在大量的重叠，大量地重叠子问题意味着大量地重复计算，这样时间复杂度很可能呈指数级上升（在下文中我们会看到多个这样重复的计算导致的指数级的时间复杂度），所以自下而上的求解方式可以消除重叠子问题。
简单总结一下，最优子结构，状态转移方程，重叠子问题就是动态规划的三要素，这其中定义子问题的状态与写出状态转移方程是解决动态规划最为关键的步骤，状态转移方程如果定义好了，解决动态规划就基本不是问题了。
算法题目描述
有 N 件物品和一个容量是 V 的背包。每件物品有且只有一件。
第 i 件物品的体积是v[i] ，价值是w[i] 。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
示例 1：
输入: N = 3, V = 4, v = [4,2,3], w = [4,2,3]
输出: 4
解释: 只选第一件物品，可使价值最大。示例 2：
输入: N = 3, V = 5, v = [4,2,3], w = [4,2,3]
输出: 5
解释: 不选第一件物品，选择第二件和第三件物品，可使价值最大。解题思路
模板代码
/**
*
* @param N 物品数
* @param C 背包容量
* @param v 每件的体积
* @param w 每件物品的价值
* @return 最大价值
*/
public int zoKnapsack(int N, int C, int[] v, int[] w) {
//0-1背包朴素
int[][] dp = new int[N][C+1];
//初始化
for (int j = 0; j <= C; j++) {
dp[0][j] = j >= v[0] ? w[0] : 0;
}
//处理剩余元素
for (int i = 1; i < N; i++) {
for (int j = 0; j <= C; j++) {
//不选
int x = dp[i-1][j];
//选
int y = j >= v[i] ? dp[i-1][j-v[i]] + w[i] : 0;
//取两者中的最大值
dp[i][j] = Math.max(x, y);
}
}
return dp[N-1][C];
}
