动态规划类问题
- 从已知子问题的解，推导出当前问题的解 推导过程可以表达为一个数学公式
- 用一维或二维数组来保存之前的计算结果（可以进一步降维优化）
将当前问题 分解成子问题 ，找出递归公式，分阶段进行求解 求解过程中缓存子问题的解，避免重复计算。
以一个简单例子Fibonacci数列为例，求Fibonacci数列第 n 项的
从第二项开始，每一项的值都等于前两项的值之和
0 1 1 2 3 5 8
dp[i] = dp[i-1] + dp[i-2]
思路：
1.若求第 0 项或第 1 项的值，直接返回对应的值 0 或 1
2.创建一个一维数组缓存第n项数值之前的求解结果，并初始化第一项和第二项的值
3.使用循环计算处每一项的值，直到第 n 项，最后返回一维数组的第n项值即可
代码：
public static int fibonacci(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
}
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}测试：
public static void main(String[] args) {
// 0 1 1 2 3 5 8
System.out.println(fibonacciDown(13)); //求第 7 项值
}降维优化：对于每个子问题只需要三个值参与，何不用三个变量代替一维数组进行优化：
/**
* 求 Fibonacci 的第 n 项 (降维)
*
* @param n 第几项
* @return
*/
public static int fibonacciDown(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
}
int a = 0, b = 1;
for (int i = 2; i <= n; i++) {
int c = a + b; //记录第i项的值
//更新值
a = b;
b = c;
}
return b;
}Leecode62. 不同路径 题
从start走到finish有多少种走法（只能向右或向下走）
将每个格子的走法都记录出来，标识数字为 start 到该格子上的有多少走法，，找出规律
可看出规律为：dp[i][j] = dp[i][j - 1] + dp[i -1][j]，并且第一行和第一列的值都为1，即走法只有一种
思路：
1.以一个二维数组缓存每个格子的走法数
2.遍历每行每列，求出每个格子的走法数
3.最后返回第m行第n列的值，即为最终结果
代码：
/**
* 求到第m行n列有多少种走法，只能向右和向下
*
* @param m
* @param n
* @return
*/
public static int uniquePaths2(int m, int n) {
int[][] dp = new int[m][n];
//初始化第一行和第一列的值为 1（其走法只有一种）
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int i = 0; i < n; i++) {
dp[0][i] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
}
}
print(dp);
return dp[m - 1][n - 1];
}降维优化：
每次计算当前格子的走法数时，只需要上一个格子和左边格子的走法之和，何不使用一维数组，上一个格子的走法即为当前格子的做法，将dp[i][j] = dp[i][j - 1] + dp[i -1][j]改为dp[j] = dp[j] + dp[j - 1]，实现降维优化的目的，以第二行到第三行为例：
代码：
/**
* 求到第m行n列有多少种走法，只能向右和向下 (降维，二维 变 一维)
*
* @param m
* @param n
* @return
*/
public static int uniquePaths(int m, int n) {
int[] dp = new int[n];
//初始化第一行和第一列的值为 1（其走法只有一种）
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] = dp[j] + dp[j - 1]; //自己加上 上一列的
}
}
// System.out.println(Arrays.toString(dp));
return dp[n - 1];
}2. 01背包问题 - AcWing题库
从N个物体中选择物体放入体积为V的背包中，使得价值最大，每种物品只能选择一次
以一下测试示例：
4 5 //物体数量为 4，背包体积为 5
1 2 //第一个物体的体积 1 和价值 2
2 4
3 4
4 5以一个二维数组缓存第一行只有物品A的选择，第二行只有物体A、B时的选择等..，
ABCD分别表示四个物体
二维数组 dp 中：
第一行中选择物体A，体积为1，在体积为0时不能放下为0，其它都能放下A
第二行中选择物体B，体积为2，在背包体积为0、1时不能放下，将上一行数据复制下来，背包体积为2时能放下，价值为2比上一行的A更大，为3、4、5时可以放下B此外还能放下一个物体A
第三行中选择物体C，体积为3，在背包体积为0、1、2时不能放下，将上一行数据复制下来，在背包体积 为3是虽然能放下C，但是上一行的BA价值是6，比C的价值大，所以直接复制下来，在体积为5时，当前背包除了能放下BA外还能放下一个C
第四行选择物体D，体积为4，在背包体积为0、1、2、3时不能放下，将上一行数据复制下来，在背包体积 为4是虽然能放下D，但是上一行的BA价值是6，比D的价值大，所以直接复制下来，在体积为5时同理
编号 体积(g) 价值(元) 物品名
1 1 2 A
2 2 4 B
3 3 4 C
4 4 5 D
二维数组 dp ：
0 1 2 3 4 5 --> 背包体积
0 0 A A A A A A
1 0 A B BA BA BA B
2 0 A B BA BA BAC C
3 0 A B BA BA BAC D
0, 2, 2, 2, 2, 2
0, 2, 4, 6, 6, 6
0, 2, 4, 6, 6, 8
0, 2, 4, 6, 6, 8
结果：8 (BAC)总结一个规律：
1.装得下 —— 当前物品价值比上一行价值更大时，选择当前物品，再加上总体积 - 当前物品体积得到的体积值列中最大价值得物品，加到当前处
dp[i][j] = Math.max(dp[i-1][j],currItemValue + dp[i-1][jTotal - currItem.weight]) 比如dp数组中：dp[1][3] = Max(dp[0][3],B + dp[0][3-2]) = BA
2.装不下,将上一行物品复制下来
dp[i][j] = dp[i-1][j]
代码二维：
import java.util.Scanner;
/**
* 0 - 1背包问题
*/
public class Main {
public static void main(String[] args) {
/*
编号 体积(g) 价值(元) 物品名
1 1 2 A
2 2 4 B
3 3 4 C
4 4 5 D
0 1 2 3 4 5 --> 体积
0 0 A A A A A A
1 0 A B BA BA BA B
2 0 A B BA BA BAC C
3 0 A B BA BA BAC D
0, 2, 2, 2, 2, 2
0, 2, 4, 6, 6, 6
0, 2, 4, 6, 6, 8
0, 2, 4, 6, 6, 8
结果：8 (BAC)
1.装得下 —— 当前物品价值比上一行价值更大时，选择当前物品，再加上总体积 - 当前物品体积量得到得体积列中最大价值得物品，加到当前处
dp[i][j] = Max(dp[i-1][j],currItemValue + dp[i-1][jTotal - currItem.weight]) 比如：dp[3][8] = Max(dp[2][8],D + dp[2][8-1]) = DA
2.装不下,将上一行物品复制下来
dp[i][j] = dp[i-1][j]
*/
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); //物品数量
int V = sc.nextInt(); //背包容积
int[] vArr = new int[N]; //N个物品的体积
int[] pArr = new int[N]; //N个物品的价值
for (int i = 0; i < N; i++) {
vArr[i] = sc.nextInt();
pArr[i] = sc.nextInt();
}
System.out.println(knapsackProblem01(V, vArr, pArr, N));
}
public static int knapsackProblem01(int V, int[] vArr, int[] pArr, int N) {
int[][] dp = new int[N][V + 1];
for (int j = 0; j < V + 1; j++) {
if (vArr[0] <= j) { //装得下
dp[0][j] = pArr[0];
}
}
for (int i = 1; i < N; i++) {
for (int j = 0; j < V+1; j++) {
int x = dp[i - 1][j]; //上一行的价值
if (vArr[i] <= j) { //装得下
// 当前物品价值 剩余物品价值
dp[i][j] = Math.max(x, pArr[i] + dp[i-1][j - vArr[i]]);
} else { //装不下
dp[i][j] = x;
}
}
}
return dp[N - 1][V];
}
}
代码（降维成一维数组）：
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); //物品数量
int V = sc.nextInt(); //背包容积
int[] vArr = new int[N]; //N个物品的体积
int[] pArr = new int[N]; //N个物品的价值
for (int i = 0; i < N; i++) {
vArr[i] = sc.nextInt();
pArr[i] = sc.nextInt();
}
int[] dp = new int[V + 1];
for (int j = 0; j < V + 1; j++) {
if (vArr[0] <= j) { //装得下
dp[j] = pArr[0];
} else { //装不下
dp[j] = 0;
}
}
//System.out.println(Arrays.toString(dp));
for (int i = 1; i < N; i++){
for (int j = V; j > 0; j--) {
if (vArr[i] <= j) { //装得下
// pArr[i]当前物品价值 dp[j - vArr[i]]剩余空间在上次中（避免同一物品重复使用）能装的最大值
dp[j] = Math.max(dp[j], pArr[i] + dp[j - vArr[i]]);
}
}
//System.out.println(Arrays.toString(dp));
}
System.out.println(dp[V]);
}
3. 完全背包问题 - AcWing题库
与01背包问题的区别：
dp[i][j] = Math.max(x, pArr[i] + dp[i][j - vArr[i]]); //完全背包中物品数量无限，从本次物品中找，同一物品可重复使用
dp[i][j] = Math.max(x, pArr[i] + dp[i-1][j - vArr[i]]); //01背包中物品数量只有一个，从上次物品中找，同一物品只能用一次
代码（二维）：
import java.util.Scanner;
/**
* 完全背包问题
*/
public class Main {
public static void main(String[] args) {
/*
编号 体积(g) 价值(元) 物品名
1 1 2 A
2 2 4 B
3 3 4 C
4 4 5 D
完全背包：
0 1 2 3 4 5 --> 体积
0 0 A AA AAA AAAA AAAAA A
1 0 A B BA BB BBA B
2 0 A B BA BB BBA C
3 0 A B BA BB BBA D
0 2 4 6 8 10 A
0 2 4 6 8 10 B
0 2 4 6 8 10 C
0 2 4 6 8 10 D
结果：10 (BAC)
1.装得下 —— 当前物品价值比上一行价值更大时，选择当前物品，再加上(总体积 - 当前物品体积)得到的体积列中最大价值得物品，加到当前处
dp[i][j] = Max(dp[i-1][j],currItemValue + dp[i-1][jTotal - currItem.weight]) 比如：dp[3][8] = Max(dp[2][8],D + dp[2][8-1]) = DA
2.装不下,将上一行物品复制下来
dp[i][j] = dp[i-1][j]
*/
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); //物品数量
int V = sc.nextInt(); //背包容积
int[] vArr = new int[N]; //N个物品的体积
int[] pArr = new int[N]; //N个物品的价值
for (int i = 0; i < N; i++) {
vArr[i] = sc.nextInt();
pArr[i] = sc.nextInt();
}
System.out.println(knapsackProblemComplete(V, vArr, pArr, N));
}
public static int knapsackProblemComplete(int V, int[] vArr, int[] pArr, int N) {
int[][] dp = new int[N][V + 1];
for (int j = 0; j < V + 1; j++) {
if (vArr[0] <= j) { //装得下
dp[0][j] = pArr[0] + dp[0][j - vArr[0]];
}
}
for (int i = 1; i < N; i++) {
for (int j = 0; j < V + 1; j++) {
int x = dp[i - 1][j]; //上一行的价值
if (vArr[i] <= j) { //装得下
// 当前物品价值 剩余体积的物品价值（从本次中找）
dp[i][j] = Math.max(x, pArr[i] + dp[i][j - vArr[i]]);
} else { //装不下
dp[i][j] = x;
}
}
}
return dp[N - 1][V];
}
}
降维：
import java.util.Scanner;
/**
* 完全背包问题
*/
public class Main {
public static void main(String[] args) {
/*
1. n个物品都是固体，有重量和价值
2. 现在你要取走不超过 10克 的物品
3. 每件物品只能使用一次
编号 体积(g) 价值(元) 物品名
1 1 2 A
2 2 4 B
3 3 4 C
4 4 5 D
完全背包：
0 1 2 3 4 5 --> 体积
0 0 A AA AAA AAAA AAAAA A
1 0 A B BA BB BBA B
2 0 A B BA BB BBA C
3 0 A B BA BB BBA D
0 2 4 6 8 10 A
0 2 4 6 8 10 B
0 2 4 6 8 10 C
0 2 4 6 8 10 D
结果：10 (BAC)
1.装得下 —— 当前物品价值比上一行价值更大时，选择当前物品，再加上总重量 - 当前物品重量得到得重量列中最大价值得物品，加到当前处
dp[i][j] = Max(dp[i-1][j],currItemValue + dp[i-1][jTotal - currItem.weight]) 比如：dp[3][8] = Max(dp[2][8],D + dp[2][8-1]) = DA
2.装不下,将上一行物品复制下来
dp[i][j] = dp[i-1][j]
4 5
1 2
2 4
3 4
4 5
*/
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); //物品数量
int V = sc.nextInt(); //背包容积
int[] vArr = new int[N]; //N个物品的体积
int[] pArr = new int[N]; //N个物品的价值
for (int i = 0; i < N; i++) {
vArr[i] = sc.nextInt();
pArr[i] = sc.nextInt();
}
System.out.println(knapsackProblemComplete2(V, vArr, pArr, N));
}
/**
* 取total重量的物品 并且 价值最大(降维)
*
* @return 最大价值
*/
public static int knapsackProblemComplete2(int V, int[] vArr, int[] pArr, int N) {
int[] dp = new int[V + 1];
for (int j = 0; j < V + 1; j++) {
if (vArr[0] <= j) { //装得下
dp[j] = pArr[0] + dp[j - vArr[0]];
}
}
for (int i = 1; i < N; i++) {
for (int j = 0; j < V + 1; j++) {
int x = dp[j]; //上一行的价值
if (vArr[i] <= j) { //装得下
// 当前物品价值 剩余物品价值
dp[j] = Math.max(x, pArr[i] + dp[j - vArr[i]]);
} else { //装不下
dp[j] = x;
}
}
// System.out.println(Arrays.toString(dp));
}
return dp[V];
}
}
