这个问题属于常用的动态规划问题，网络上已经有比较完整的讲解和代码段，若用dp[i]表示凑够i元需要的最少硬币数目，可以得到状态方程dp[i]=min{dp[i-vj]+1},其中vj表示第j个硬币的面值。
我发现网络上的大多数解法中，硬币的面额需要包括面值为1的硬币，包括了面值为1的硬币，这样dp[i]的初始化会变得比较容易:dp[i]=i，并且所有金额都会有解，例如如果给定硬币的最小金额为3元，则i在1和2时候是无解的，那么dp[1]=dp[2]=0,我不禁思考如果不包括面值为1的硬币时候，代码需要进行怎么样的改进和优化。
初始值的改变为，所有dp[i]的初始值我定义为0。判断是否有解的改进为，第一步先判断给定i元能否在包括了第j个硬币的情况下有解，若无解，则直接跳过不做任何操作，直接开始下一个硬币的判断，若有解，也分为两种情况第一种情况是这是第i元第一次被凑齐，此时的dp[i]=0，第二种情况，dp[i]不是第一次被凑齐，此时需要判断当前的解是否比之前的解要小，因为题目要求为最少的硬币数目。 代码段如下：
int sum=12;//i最多12元 int[] dp=new int[sum+1]; int[] v={3,5,11};//总共3元5元11元面额的硬币 for(int i = 1; i <= sum; i++){ for(int j = 0; j < v.length; j++){ if(i>=v[j]){ if(dp[i-v[j]]==0&&i-v[j]!=0) //判断给定i元能否在包括了第j个硬币的情况下有解 continue;//直接开始下一个硬币的判断 else if(dp[i]==0||dp[i - v[j]] + 1 < dp[i]) //i元第一次被凑齐或者i元不是第一次被凑齐，但是当前的解比之前的解要小 dp[i] = dp[i- v[j] ] + 1; } } } System.out.println(Arrays.toString(dp));运行结果为：
