回溯解法—Java
说实话,这个题目直接一次ac,满心欢喜的看看别人的题解。好家伙全是dp,我就搞不明白了,这个题目怎么直接就能想到用dp来做的?第一名的题解居然还给我搞了个线性代数的证明,真的6。直接给我干成hard题了。那种证明是我能想到的???
题解
这道题的题目写了一大堆,但是我觉得一眼就能看出来要我们求得是每个货币系统要删掉哪几个面值的货币。我第一时间能想到的是遍历,看那个面值的货币是多余的。一个货币如果是多余的,就说明一定有其他的一些面值可以凑出来这个货币。那这些其他货币一定要比这个货币要小才行。我们直接将a数组从小到大排序,然后遍历每一个货币,看这个货币是否能有前面比他小的一些货币组成就行了。
我觉得这个思路才是正常人的思路吧,我劝你们不要太神仙打架了!
dp解法
虽然我被线性代数证明劝退了,但是这毕竟是一道dp题,看了一份dp题解非常和我的心意。大概意思就是仿照上面那道简单点的货币系统题,我们只需要计算出每个货币面值在当前货币系统下的组合方式,如果组合方式只有1种,那就是不能删除的了。这个解法太酷了,但是我没有想到,很烦!!!
ps(这道题用的是回溯ac的,说实话我也是抱着试试的心态提交的,因为我回溯的时间复杂度有点子算不明白,有大佬帮算一下我这个题解的时间复杂度吗?)
import java.util.*;
public class Main{
public static int N = 110;
public static int[] a;
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int t = in.nextInt();
while(t-- > 0){
int n = in.nextInt();
int res = 0;
a = new int[n + 1];
for(int i = 1; i <= n; i++){
a[i] = in.nextInt();
}
Arrays.sort(a);
for(int i = 1; i <= n; i++){
if(dfs(i - 1, a[i])){
res++;
a[i] = 0;
}
}
System.out.println(n - res);
}
}
public static boolean dfs(int x, int target){
if(x == 0)
return false;
if(a[x] == 0)
return dfs(x - 1, target);
for(int i = 0; i * a[x] <= target; i++){
if(i * a[x] == target)
return true;
else{
boolean flag = dfs(x - 1, target - i * a[x]);
if(flag)
return true;
}
}
return false;
}
}