AcWing 1371. 货币系统(Java 二维+一维)
原题链接
简单
作者:
Limited
,
2021-02-09 22:34:11
,
所有人可见
,
阅读 309
要点
- 闫氏dp分析法
- $f(i, j)$只考虑前$i$种物品且总价值恰好为$j$的选法集合,属性:$Sum$
- $f(i, j) = f(i-1, j) + f(i-1, j-v) + f(i-1, j-2v) + \cdots + f(i-1, j-kv) + \cdots + f(i-1, j-\frac jvv)$
考虑到$f(i, j-v) = f(i-1, j-v) + f(i-1, j-2v) + \cdots + f(i-1, j-kv) + \cdots + f(i-1, j-\frac jvv)$(其中最后一项本为$f(i-1, j-(\frac jv+1)v)$,但明显$j-(\frac jv+1)v) < 0$故舍去,–$_{我猜的, 劳烦指正}$) 所以$f(i, j) = f(i-1, j) + f(i-1, j-v)$(注意当且仅当j>=v时第二项有效)
- 初始状态$f(0, 0)=1$,即只考虑前0种物品(无物品)且总价值恰好为0的选法有1种,其实$\forall 0 \leq i \leq n, f(i, 0)=0$,但状态转移时只考虑上层状态和本层已推导的,所以只需要指定$f(0,0)$即可
- 空间优化 二维数组转一维 代码等价替换即可
DP 二维数组
import java.lang.*;
import java.util.*;
public class Main {
static Scanner scanner = new Scanner(System.in);
static int n, m;
// 答案数值很大 爆int 类型long
static long[][] f = new long[30][10010];
public static void main(String[] args) {
n = scanner.nextInt();
m = scanner.nextInt();
// 初始状态f[0][0] 只考虑前0种且总价值恰好为0的选法有1种
// 其实对于任何0<=i<=n 都有f[i][0]=1
// 但【f[i][j]=f[i-1][j]+f[i][j-w]】只需考虑"上一层"和"本层已推导的" 所以赋值i=0的情况即可
f[0][0] = 1;
for (int i = 1; i <= n; i++) {
int w = scanner.nextInt();
for (int j = 0; j <= m; j++) {
// f[i][j]=f[i-1][j]+f[i][j-w] 拆分 当且仅当j>=w时 f[i][j-w]有效
f[i][j] = f[i - 1][j];
if (j >= w) {
f[i][j] += f[i][j - w];
}
}
}
System.out.println(f[n][m]);
}
}
DP 一维数组 空间优化
import java.lang.*;
import java.util.*;
public class Main {
static Scanner scanner = new Scanner(System.in);
static int n, m;
static long[] f = new long[10010];
public static void main(String[] args) {
n = scanner.nextInt();
m = scanner.nextInt();
f[0] = 1;
for (int i = 1; i <= n; i++) {
int w = scanner.nextInt();
for (int j = w; j <= m; j++) {
f[j] += f[j - w];
}
}
System.out.println(f[m]);
}
}