dp数组的初始化、状态转移方程、遍历顺序至关重要
其中的关键是状态转移方程，初始化以及遍历顺序都由状态转移方程确定
01背包
01背包-二维dp数组(m行)
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| package 背包;
public class bag01_2d {
public static void main(String[] args) {
int[] weight = {4, 1, 3};
int[] value = {30, 15, 20};
int capacity = 4;
int res = calcMaxValue(weight, value, capacity);
System.out.println("res: " + res);
}
private static int calcMaxValue(int[] weight, int[] value, int capacity) {
int[][] dp = new int[weight.length][capacity + 1];
for (int j = 0; j <= capacity; ++j)
dp[0][j] = j >= weight[0] ? value[0] : 0;
for (int i = 1; i < weight.length; ++i) {
for (int j = 1; j <= capacity; ++j) {
if (j >= weight[i])
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
else
dp[i][j] = dp[i - 1][j];
}
}
for (int i = 0; i < weight.length; ++i) {
for (int j = 0; j <= capacity; ++j)
System.out.print(dp[i][j] + "\t");
System.out.println();
}
System.out.println();
return dp[weight.length - 1][capacity];
}
}
|
输出
1
2
3
4
5
| 0 0 0 0 30
0 15 15 15 30
0 15 15 20 35
res: 35
|
01背包-二维dp数组(两行)
状态转移：
1
2
3
4
| if(j >= weight[i])
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]) 选物品i或不选物品i
else
dp[i][j] = dp[i - 1][j] 不选物品i
|
可以看出dp[i][j]只可能被dp[i - 1][j]和dp[i - 1][j - weight[i]]推导出，也就是说第i行只与第i - 1行关联，那么dp数组只需要用两行
与使用m行的代码相比，只需要将dp数组更改为2行，dp[i]与dp[i - 1]改为dp[i % 2]与dp[(i - 1) % 2]
初始化后(遍历完第0个物品后)的dp数组为
遍历完第1个物品后的dp数组为
1
2
| 0 0 0 0 30
0 15 15 15 30
|
遍历第2个物品时，只需要遍历第1个物品的dp数据，不需要遍历第0个物品的dp数据，所以把遍历第2个物品的dp数据覆盖在第0行
1
2
| 0 0 0 20 35
0 15 15 15 30
|
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| package 背包;
public class bag01_2d {
public static void main(String[] args) {
int[] weight = {4, 1, 3};
int[] value = {30, 15, 20};
int capacity = 4;
int res = calcMaxValue(weight, value, capacity);
System.out.println("res: " + res);
}
private static int calcMaxValue(int[] weight, int[] value, int capacity) {
int[][] dp = new int[2][capacity + 1];
for (int j = 0; j <= capacity; ++j)
dp[0][j] = j >= weight[0] ? value[0] : 0;
for (int i = 1; i < weight.length; ++i) {
for (int j = weight[i]; j <= capacity; ++j) {
dp[i % 2][j] = Math.max(dp[(i - 1) % 2][j], dp[(i - 1) % 2][j - weight[i]] + value[i]);
}
}
for (int i = 0; i < 2; ++i) {
for (int j = 0; j <= capacity; ++j)
System.out.print(dp[i][j] + "\t");
System.out.println();
}
System.out.println();
return dp[(weight.length - 1) % 2][capacity];
}
}
|
输出
1
2
3
4
| 0 0 0 20 35
0 15 15 15 30
res: 35
|
01背包-滚动数组(一维dp数组)
两行能搞定，一行也行！
现在使用一维dp数组
1
| int[] dp = new int[capacity + 1];
|
回顾一下使用二维dp数组是如何填表的
1
2
3
4
5
6
| 0 0 0 0 30
0 15 15 15 30
0 15 15 20 35
// int[] weight = {4, 1, 3};
// int[] value = {30, 15, 20};
// int capacity = 4;
|
直接看第二行最后一个元素35(此时i = 2, j = 4)，它是由dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);更新
dp[i - 1][j - weight[i]] = dp[1][1] = 15, value[i] = 20
35是由左上方的15加上value[2]得到的
所以使用一维滚动数组，在更新dp[4]的时候(相对于两维数组是要更新dp[2][4])，
需要上一行的dp[1](相对于二维dp数组是dp[1][1])，
那么j的遍历顺序一定要从后往前！否则(从前往后)，dp[1]是二维dp数组中dp[2][1]的数据
1
| for (int j = capacity; j >= weight[i]; --j)
|
代码
初始化为0即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| package 背包;
public class bag01 {
public static void main(String[] args) {
int[] weight = {4, 1, 3};
int[] value = {30, 15, 20};
int capacity = 4;
int res = calcMaxValue(weight, value, capacity);
System.out.println(res);
}
private static int calcMaxValue(int[] weight, int[] value, int capacity) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < weight.length; ++i)
for (int j = capacity; j >= weight[i]; --j)
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
for (int j = 0; j <= capacity; j++){
System.out.print(dp[j] + " ");
}
return dp[capacity];
}
}
|
输出
方法一：记忆化搜索背包
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public int findTargetSumWays(int[] nums, int target) {
this.nums = nums;
n = nums.length;
for (int x : nums)
target += x;
if (target % 2 != 0 || target < 0)
return 0;
target /= 2;
dp = new int[n][target + 1];
for (int[] arr : dp)
Arrays.fill(arr, -1);
return dfs(0, target);
}
private int dfs(int index, int target) {
if (index == n)
return target == 0 ? 1 : 0;
if (dp[index][target] != -1)
return dp[index][target];
int choose = 0, pass = dfs(index + 1, target);
if (target >= nums[index])
choose = dfs(index + 1, target - nums[index]);
return dp[index][target] = pass + choose;
}
int[] nums;
int n;
int[][] dp;
}
|
方法二：01背包
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int findTargetSumWays(int[] nums, int target) {
int n = nums.length;
for (int x : nums)
target += x;
if (target % 2 != 0 || target < 0)
return 0;
target /= 2;
int[][] dp = new int[n + 1][target + 1];
dp[0][0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= target; ++j) {
dp[i + 1][j] = dp[i][j];
if (j >= nums[i])
dp[i + 1][j] += dp[i][j - nums[i]];
}
}
return dp[n][target];
}
}
|
方法三：滚动数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int findTargetSumWays(int[] nums, int target) {
int n = nums.length;
for (int x : nums)
target += x;
if (target % 2 != 0 || target < 0)
return 0;
target /= 2;
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 0; i < n; ++i)
for (int j = target; j >= nums[i]; --j)
dp[j] += dp[j - nums[i]];
return dp[target];
}
}
|
方法一：记忆化搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public int coinChange(int[] coins, int amount) {
this.coins = coins;
n = coins.length;
dp = new int[n][amount + 1];
for (int[] arr : dp)
Arrays.fill(arr, -1);
int res = dfs(0, amount);
return res == Integer.MAX_VALUE / 2 ? -1 : res;
}
private int dfs(int index, int amount) {
if (index == n)
return amount == 0 ? 0 : Integer.MAX_VALUE / 2;
if (dp[index][amount] != -1)
return dp[index][amount];
if (coins[index] > amount)
return dfs(index + 1, amount);
return dp[index][amount] = Math.min(dfs(index + 1, amount), dfs(index, amount - coins[index]) + 1);
}
int[] coins;
int n;
int[][] dp;
}
|
方法二：完全背包
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int coinChange(int[] coins, int amount) {
int n = coins.length;
int[][] dp = new int[n + 1][amount + 1];
for (int[] arr : dp)
Arrays.fill(arr, Integer.MAX_VALUE >> 1);
dp[0][0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= amount; ++j) {
dp[i + 1][j] = dp[i][j];
if (coins[i] <= j)
dp[i + 1][j] = Math.min(dp[i][j], dp[i + 1][j - coins[i]] + 1);
}
}
return dp[n][amount] == Integer.MAX_VALUE >> 1 ? -1 : dp[n][amount];
}
}
|
方法三：滚动数组
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int coinChange(int[] coins, int amount) {
int n = coins.length;
int[] dp = new int[amount + 1];
Arrays.fill(dp, Integer.MAX_VALUE >> 1);
dp[0] = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j <= amount; ++j)
if (j >= coins[i])
dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
return dp[amount] == Integer.MAX_VALUE >> 1 ? -1 : dp[amount];
}
}
|
方法一：01背包
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int numberOfWays(int n, int x) {
int mod = (int) 1e9 + 7;
int[][] dp = new int[n + 1][n + 1];
dp[0][0] = 1;
for (int i = 1; i <= n; ++i) {
int s = (int) Math.pow(i, x);
for (int j = 0; j <= n; ++j) {
dp[i][j] = dp[i - 1][j];
if (j >= s)
dp[i][j] = (dp[i][j] + dp[i - 1][j - s]) % mod;
}
}
return dp[n][n];
}
}
|
方法二：滚动数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int numberOfWays(int n, int x) {
int mod = (int) 1e9 + 7;
int[] dp = new int[n + 1];
dp[0] = 1;
for (int i = 1; i <= n; ++i) {
int s = (int) Math.pow(i, x);
for (int j = n; j >= s; --j) {
dp[j] = (dp[j] + dp[j - s]) % mod;
}
}
return dp[n];
}
}
|
方法三：静态处理
所有x,n在static语句块中处理好
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
static int[][] dp;
static {
int n = 300, x = 5;
int mod = (int) 1e9 + 7;
dp = new int[x][n + 1];
for (int i = 0; i < x; ++i)
dp[i][0] = 1;
for (int k = 1; k <= x; ++k) {
for (int i = 1; i <= n; ++i) {
int s = (int) Math.pow(i, k);
for (int j = n; j >= s; --j) {
dp[k - 1][j] = (dp[k - 1][j] + dp[k - 1][j - s]) % mod;
}
}
}
}
public int numberOfWays(int n, int x) {
return dp[x - 1][n];
}
}
|
方法一：记忆化搜索(爆内存)
方案数用 +！！！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
this.group = group;
this.profit = profit;
this.n = n;
this.minProfit = minProfit;
dp = new int[group.length][n + 1][10000];
for (int[][] a : dp)
for (int[] b : a)
Arrays.fill(b, -1);
return dfs(0, n, 0);
}
public int dfs(int index, int hc, int p) {
if (index == group.length)
return p >= minProfit ? 1 : 0;
if (dp[index][hc][p] != -1)
return dp[index][hc][p];
int x = group[index], y = profit[index];
if (hc >= x)
return dp[index][hc][p] = (dfs(index + 1, hc, p) + dfs(index + 1, hc - x, p + y)) % mod;
return dp[index][hc][p] = dfs(index + 1, hc, p) % mod;
}
int[] group, profit;
int n, minProfit, mod = (int) 1e9 + 7;
int[][][] dp;
}
|
方法二：10000改成sum
勉勉强强过
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
this.group = group;
this.profit = profit;
this.n = n;
this.minProfit = minProfit;
int sum = 0;
for (int x : profit)
sum += x;
dp = new int[group.length][n + 1][sum + 1];
for (int[][] a : dp)
for (int[] b : a)
Arrays.fill(b, -1);
return dfs(0, n, 0);
}
public int dfs(int index, int hc, int p) {
if (index == group.length)
return p >= minProfit ? 1 : 0;
if (dp[index][hc][p] != -1)
return dp[index][hc][p];
int x = group[index], y = profit[index];
if (hc >= x)
return dp[index][hc][p] = (dfs(index + 1, hc, p) + dfs(index + 1, hc - x, p + y)) % mod;
return dp[index][hc][p] = dfs(index + 1, hc, p) % mod;
}
int[] group, profit;
int n, minProfit, mod = (int) 1e9 + 7;
int[][][] dp;
}
|
方法三：01背包
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
int sum = 0, mod = (int) 1e9 + 7;
for (int x : profit)
sum += x;
int[][][] dp = new int[group.length + 1][n + 1][minProfit + 1];
for (int i = 0; i <= n; ++i)
dp[0][i][0] = 1;
for (int i = 1; i <= group.length; ++i) {
int x = group[i - 1], y = profit[i - 1];
for (int j = 0; j <= n; ++j) {
for (int k = 0; k <= minProfit; ++k) {
dp[i][j][k] = dp[i - 1][j][k];
if (j >= x)
dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - x][Math.max(0, k - y)]) % mod;
}
}
}
return dp[group.length][n][minProfit];
}
}
|
方法一：记忆化搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
static int[] nums = new int[10000];
static {
for (int i = 1; i < nums.length; ++i)
nums[i] = i * i;
}
public int numSquares(int n) {
this.n = n;
m = (int) Math.sqrt(n);
for (int i = 1; i <= n; ++i)
nums[i] = i * i;
dp = new int[m + 1][n + 1];
for (int[] arr : dp)
Arrays.fill(arr, -1);
return dfs(1, n);
}
int n, m, inf = Integer.MAX_VALUE / 2;
int[][] dp;
public int dfs(int index, int sum) {
if (index == m + 1)
return sum == 0 ? 0 : inf;
if (dp[index][sum] != -1)
return dp[index][sum];
int x = nums[index];
if (sum >= x)
return dp[index][sum] = Math.min(dfs(index, sum - x) + 1, dfs(index + 1, sum));
return dp[index][sum] = dfs(index + 1, sum);
}
}
|
方法二：完全背包
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int numSquares(int n) {
int m = (int) Math.sqrt(n);
int[] dp = new int[n + 1];
Arrays.fill(dp, 100010);
dp[0] = 0;
for (int i = 1; i <= m; ++i) {
int x = i * i;
for (int j = x; j <= n; ++j) {
dp[j] = Math.min(dp[j], dp[j - x] + 1);
}
}
return dp[n];
}
}
|