题解 | #找硬币#

*题目其实说的很模糊，我抄答案（看别人写的提交）的时候才发现有很多隐含条件，比方说最大硬币金额不能超过兔子的最大单只金额

dp[i]定义为硬币最大为i的时候所需的硬币数目

初始化dp[1]=1

import java.util.*;
public class Main{
    public static void main(String[] args){
      Scanner in=new Scanner(System.in);
        int count=in.nextInt();
        int sum=0;
        int max=0;
        int[] rabbit=new int[count];
        for(int i=0;i<count;i++){
            rabbit[i]=in.nextInt();
            sum+=rabbit[i];
            max=Math.max(rabbit[i],max);
        }
        System.out.println(new Main().getRes(sum,max,rabbit));
    }
    public int getRes(int sum,int max,int[] rabbit){
            int[] dp=new int[max+1];//最大面额为i需要的最少硬币数目
        dp[1]=sum;
        for(int i=2;i<=max;i++){
            dp[i]=Integer.MAX_VALUE;
        }
        for(int i=1;i<=max;i++){
            //次大面额为i
            for(int j=2;i*j<=max;j++){
                //最大面额为i*j
                int count=0;
                for(int k=0;k<rabbit.length;k++){
                    //每使用一个i*j，就少使用j个i，所以减少的硬币数就是（rabbit[k]/(i*j)）*(j-1)
                    count+=(rabbit[k]/(i*j))*(j-1);
                }
                dp[i*j]=Math.min(dp[i*j],dp[i]-count);
            }
        }
        int min=Integer.MAX_VALUE;
        for(int i=1;i<=max;i++){
            min=Math.min(dp[i],min);
        }
        return min;
    }
}

存疑，为什么

for(int k=0;k<rabbit.length;k++){
                    //每使用一个i*j，就少使用j个i，所以减少的硬币数就是（rabbit[k]/(i*j)）*(j-1)
                    count+=(rabbit[k]/(i*j))*(j-1);
                }

改成

count=(sum/(i*j))*(j-1);

结果就不对了，明明数学推导能推导成功