# maximum value minimum value

## complete knapsack problem

### analyze

state representation

• v ( i ) v(i) v(i): the first i i i object volumes
• w ( i ) w(i) w(i): the first i i i object values
• f ( i , j ) f(i,j) f(i,j): before i i i items are selected, the volume does not exceed j j maximum value of j

State transfer: as long as the backpack can fit, you can choose k k k th i i i items. both satisfied j ≥ k v ( i ) j \ge k v(i) j≥kv(i), which can be obtained from f ( i − 1 , j − k v ( i ) ) f(i - 1, j - kv(i)) f(i−1,j−kv(i)) shift. k ≥ 0 k \ge 0 k≥0

### code

```import java.util.*;

public class Main {
public static int dp(int[] v, int[] w, int n, int m) {
int[][] f = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
for (int k = 0; j >= k * v[i]; k++) {
f[i][j] = Math.max(f[i - 1][j - k * v[i]] + k * w[i], f[i][j]);
}
}
}
return f[n][m];
}

// for IO
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] v = new int[n + 1];
int[] w = new int[n + 1];
for (int i = 1; i <= n; i++) {
v[i] = scanner.nextInt();
w[i] = scanner.nextInt();
}
System.out.println(dp(v, w, n, m));
}
}
```

### optimization

formula equivalent deformation

1. f ( i , j ) = m a x ( f ( i − 1 , j ) , f ( i − 1 , j − v ( i ) ) + w ( i ) , . . . , f ( i − 1 , j − k v ( i ) ) + k w ( i ) , . . . ) f(i,j)=max(f(i-1,j),f(i-1,j-v(i))+w(i),...,f(i-1,j-kv(i))+kw(i),...) f(i,j)=max(f(i−1,j),f(i−1,j−v(i))+w(i),...,f(i−1,j−kv(i))+kw(i),...)

2. f ( i , j − v ( i ) ) + w ( i ) = m a x ( f ( i − 1 , j − v ( i ) ) + w ( i ) , f ( i − 1 , j − 2 v ( i ) ) + 2 w ( i ) , . . . , f ( i − 1 , j − ( k + 1 ) v ( i ) ) + ( k + 1 ) w ( i ) , . . . ) f(i,j-v(i)) + w(i)=max(f(i-1,j-v(i)) + w(i),f(i-1,j-2v(i))+2w(i),...,f(i-1,j-(k+1)v(i))+(k+1)w(i),...) f(i,j−v(i))+w(i)=max(f(i−1,j−v(i))+w(i),f(i−1,j−2v(i))+2w(i),...,f(i−1,j−(k+1)v(i))+(k+1)w(i),...)

Comparing 1 and 2, it is found that the max in 1 is the same as 2 from the second item, so there is f ( i , j ) = m a x ( f ( i − 1 , j ) , f ( i , j − v ( i ) ) + w ( i ) ) f(i,j)=max(f(i-1,j),f(i,j-v(i))+w(i)) f(i,j)=max(f(i−1,j),f(i,j−v(i))+w(i))

```public static int dp(int[] v, int[] w, int n, int m) {
int[][] f = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
f[i][j] = f[i - 1][j];
if (j >= v[i]) f[i][j] = Math.max(f[i - 1][j], f[i][j - v[i]] + w[i]);
}
}
return f[n][m];
}
```

Optimization space

```public static int dp(int[] v, int[] w, int n, int m) {
int[] f = new int[m + 1];
for (int i = 1; i <= n; i++) {
for (int j = v[i]; j <= m; j++) {
f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
}
}
return f[m];
}
```

## change

### analyze

state representation

• q ( i ) q(i) q(i): the first i i i coin denominations ( i i i from 0 0 0 starts)
• f ( i , j ) f(i,j) f(i,j): before i i i coins are chosen, and the amount is exactly j j Minimum number of coins for j

State transition: As long as the total value of the selected coins does not exceed the target value, you can select k k k th i i i items. both satisfied j ≥ k q ( i − 1 ) j \ge k q(i-1) j≥kq(i−1), can be obtained from f ( i − 1 , j − k q ( i − 1 ) ) f(i - 1, j - kq(i-1)) f(i−1,j−kq(i−1)) shift. k ≥ 0 k \ge 0 k≥0

### code

```class Solution {
public int coinChange(int[] q, int x) {
if (x == 0) return 0;
int n = q.length;

int[][] f = new int[n + 1][x + 1];

// Find the minimum value, so initialize to positive infinity
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= x; j++) f[i][j] = 0x3f3f3f;
}

// When the first coin is selected, the number of coins that can be collected for x
for (int j = 0; j <= x; j++) {
if (j % q[0] == 0) f[1][j] = j / q[0];
}

for (int i = 2; i <= n; i++) {
for (int j = 0; j <= x; j++) {
for (int k = 0; j >= k * q[i - 1]; k++) {
f[i][j] = Math.min(f[i][j], f[i - 1][j - k * q[i - 1]] + k);
}
}
}

return f[n][x] == 0x3f3f3f ? -1 : f[n][x];
}
}
```

### optimization

formula equivalent deformation

1. f ( i , j ) = m i n ( f ( i − 1 , j ) , f ( i − 1 , j − q ( i − 1 ) ) + 1 , f ( i − 1 , j − 2 q ( i − 1 ) ) + 2 , . . . ) f(i,j) = min(f(i-1,j), f(i - 1,j - q(i - 1)) + 1,f(i-1,j-2q(i-1))+2,...) f(i,j)=min(f(i−1,j),f(i−1,j−q(i−1))+1,f(i−1,j−2q(i−1))+2,...)
2. f ( i , j − q ( i − 1 ) ) + 1 = m i n ( f ( i − 1 , j − q ( i − 1 ) ) + 1 , f ( i − 1 , j − 2 q ( i − 1 ) ) + 2 , . . . ) f(i,j - q(i - 1)) + 1 = min(f(i - 1,j - q(i - 1)) + 1, f(i - 1,j - 2q(i - 1)) + 2, ...) f(i,j−q(i−1))+1=min(f(i−1,j−q(i−1))+1,f(i−1,j−2q(i−1))+2,...)

Comparing 1 and 2, it is found that the min of 1 is the same as 2 from the second item, so there is f ( i , j ) = m i n ( f ( i − 1 , j ) , f ( i , j − q ( i − 1 ) ) + 1 ) f(i,j) = min(f(i-1,j) , f(i,j-q(i-1)) + 1) f(i,j)=min(f(i−1,j),f(i,j−q(i−1))+1)

```class Solution {
public int coinChange(int[] q, int x) {
if (x == 0) return 0;
int n = q.length;

int[][] f = new int[n + 1][x + 1];

for (int i = 0; i <= n; i++) {
for (int j = 0; j <= x; j++) f[i][j] = 0x3f3f3f;
}

for (int j = 0; j <= x; j++) {
if (j % q[0] == 0) f[1][j] = j / q[0];
}

for (int i = 2; i <= n; i++) {
for (int j = 0; j <= x; j++) {
f[i][j] = f[i - 1][j];
if (j >= q[i - 1]) f[i][j] = Math.min(f[i - 1][j], f[i][j - q[i - 1]] + 1);
}
}

return f[n][x] == 0x3f3f3f ? -1 : f[n][x];
}
}
```

Optimization space

```class Solution {
public int coinChange(int[] q, int x) {
if (x == 0) return 0;
int n = q.length;

int[] f = new int[x + 1];

for (int j = 0; j <= x; j++) {
f[j] = j % q[0] == 0 ? j / q[0] : 0x3f3f3f;
}

for (int i = 2; i <= n; i++) {
for (int j = q[i - 1]; j <= x; j++) {
f[j] = Math.min(f[j], f[j - q[i - 1]] + 1);
}
}

return f[x] == 0x3f3f3f ? -1 : f[x];
}
}
```

# number of plans

## monetary system

### analyze

state representation

• v ( i ) v(i) v(i): the first i i i currency denominations
• f ( i , j ) f(i,j) f(i,j): before i i i currencies are chosen with a face value of exactly j j number of options for j

State transfer: as long as the backpack can fit, you can choose k k k th i i i currencies. both satisfied j ≥ k v ( i ) j \ge k v(i) j≥kv(i), which can be obtained from f ( i − 1 , j − k v ( i ) ) f(i - 1, j - kv(i)) f(i−1,j−kv(i)) shift. k ≥ 0 k \ge 0 k≥0

### code

```import java.util.*;

public class Main {
public static long dp(int[] v, int n, int m) {
long[][] f = new long[n + 1][m + 1];
f[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
for (int k = 0; j >= k * v[i]; k++) {
f[i][j] += f[i - 1][j - k * v[i]];
}
}
}
return f[n][m];
}

// for IO
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] v = new int[n + 1];
for (int i = 1; i <= n; i++) {
v[i] = scanner.nextInt();
}
System.out.println(dp(v, n, m));
}
}
```

### optimization

formula equivalent deformation

1. f ( i , j ) = f ( i − 1 , j ) + f ( i − 1 , j − v ( i ) ) + . . . + f ( i − 1 , j − k v ( i ) ) + . . . f(i,j)=f(i-1,j) + f(i-1,j-v(i)) + ... + f(i-1,j-kv(i)) + ... f(i,j)=f(i−1,j)+f(i−1,j−v(i))+...+f(i−1,j−kv(i))+...

2. f ( i , j − v ( i ) ) = f ( i − 1 , j − v ( i ) ) + f ( i − 1 , j − 2 v ( i ) ) + . . . + f ( i − 1 , j − ( k + 1 ) v ( i ) ) + . . . f(i,j-v(i)) = f(i-1,j-v(i)) + f(i-1,j-2v(i)) + ... + f(i-1,j-(k+1)v(i)) + ... f(i,j−v(i))=f(i−1,j−v(i))+f(i−1,j−2v(i))+...+f(i−1,j−(k+1)v(i))+...

Comparing 1 and 2, it is found that 1 is the same as 2 from the second term, so there is f ( i , j ) = f ( i − 1 , j ) + f ( i , j − v ( i ) ) f(i,j) = f(i-1,j) + f(i,j-v(i)) f(i,j)=f(i−1,j)+f(i,j−v(i))

```public static long dp(int[] v, int n, int m) {
long[][] f = new long[n + 1][m + 1];
f[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
f[i][j] = f[i - 1][j];
if (j >= v[i]) f[i][j] += f[i][j - v[i]];
}
}
return f[n][m];
}
```

Optimization space

```public static long dp(int[] v, int n, int m) {
long[] f = new long[m + 1];
f[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = v[i]; j <= m; j++) {
f[j] += f[j - v[i]];
}
}
return f[m];
}
```

## Change Exchange II

### analyze

state representation

• q ( i ) q(i) q(i): the first i i i coin denominations ( i i i from 0 0 0 starts)
• f ( i , j ) f(i,j) f(i,j): before i i i coins are chosen, and the amount is exactly j j number of options for j

State transition: As long as the total value of the selected coins does not exceed the target value, you can select k k k th i i i items. both satisfied j ≥ k q ( i − 1 ) j \ge k q(i-1) j≥kq(i−1), can be obtained from f ( i − 1 , j − k q ( i − 1 ) ) f(i - 1, j - kq(i-1)) f(i−1,j−kq(i−1)) shift. k ≥ 0 k \ge 0 k≥0

### code

```class Solution {
public int change(int x, int[] q) {
int n = q.length;
int[][] f = new int[n + 1][x + 1];
f[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= x; j++) {
for (int k = 0; j >= k * q[i - 1]; k++) {
f[i][j] += f[i - 1][j - k * q[i - 1]];
}
}
}
return f[n][x];
}
}
```

### optimization

formula equivalent deformation

1. f ( i , j ) = f ( i − 1 , j ) + f ( i − 1 , j − q ( i − 1 ) ) + f ( i − 1 , j − 2 q ( i − 1 ) ) + . . . f(i,j)=f(i-1,j) + f(i-1,j-q(i-1)) + f(i-1,j-2q(i-1)) + ... f(i,j)=f(i−1,j)+f(i−1,j−q(i−1))+f(i−1,j−2q(i−1))+...

2. f ( i , j − q ( i − 1 ) ) = f ( i − 1 , j − q ( i − 1 ) ) + f ( i − 1 , j − 2 q ( i − 1 ) ) + . . . f(i,j-q(i-1)) = f(i-1,j-q(i-1)) + f(i-1,j-2q(i-1)) + ... f(i,j−q(i−1))=f(i−1,j−q(i−1))+f(i−1,j−2q(i−1))+...

Comparing 1 and 2, it is found that 1 is the same as 2 from the second term, so there is f ( i , j ) = f ( i − 1 , j ) + f ( i , j − q ( i − 1 ) ) f(i,j) = f(i-1,j) + f(i,j-q(i-1)) f(i,j)=f(i−1,j)+f(i,j−q(i−1))

```class Solution {
public int change(int x, int[] q) {
int n = q.length;
int[][] f = new int[n + 1][x + 1];
f[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= x; j++) {
f[i][j] = f[i - 1][j];
if (j >= q[i - 1]) f[i][j] = f[i - 1][j] + f[i][j - q[i - 1]];
// f[i][j]            = f[i - 1][j] + f[i - 1][j - q[i - 1]] + f[i - 1][j - 2*q[i - 1]] + ...
// f[i][j - q[i - 1]] =               f[i - 1][j - q[i - 1]] + f[i - 1][j - 2*q[i - 1]] + ...
// f[i][j] = f[i - 1][j] + f[i][j - q[i - 1]]
}
}
return f[n][x];
}
}
```

Optimization space

```class Solution {
public int change(int x, int[] q) {
int n = q.length;
// Direct dimensionality reduction
int[] f = new int[x + 1];
f[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = q[i - 1]; j <= x; j++) {
f[j] += f[j - q[i - 1]];
}
}
return f[x];
}
}
```