零钱兑换.png
最近leetcode上刷了点题目。
给自己定了一个规则：如果思考20分钟没有思路，再去网上找别人的解题过程。然后有思路了之后，30分钟内要解决问题。
但是这道动态规划，思路想了5分钟就有了（动态规划+对每一个硬币遍历，寻找最小解），但是实现的过程中，总是感觉不对。于是便写一篇文章记录一下思路和解题过程。
首先，题目看完就知道是动态规划类的题目。
首先用dp二维数组 dp[i][j] 表示 当硬币组合为0-i时，金额为j时的最小硬币数。
状态转移方程为 ：dp[i][j] = min(dp[i-1][j] , dp[i][j-coins[i]] + 1)
而动态规划二维数组往往都能优化成一维数组。
即dp[i]表示当有i这么多钱时所需最少的硬币数量。
状态转移方程为dp[i] = min(dp[i] , dp[i - coins[j] + 1)，其中j为遍历过程中的硬币数组下标。而这个是求最小值的，所以每一个元素初始赋值为amout + 1。因为硬币的面额都是大于等于1的，所以当最终结果如果等于amout +1，即表示没有该组合，返回-1.
下面是ac代码以及自测代码：
public class CoinChange {
public static void main(String[] args) {
int [] a = {1,2,5};
System.out.println(coinChange(a,11));
}
public static int coinChange(int[] coins, int amount) {
int [] dp = new int [amount + 1];
for (int i = 0;i < amount + 1;i++) {
dp[i] = amount + 1;
}
dp[0] = 0;
for (int i = 0;i < coins.length;i++) {
for (int j = coins[i];j < amount + 1;j++) {
dp[j] = Math.min(dp[j],dp[j-coins[i]] + 1);
}
}
return dp[amount] == amount + 1 ? -1 : dp[amount];
}
}
