最少的硬币数目(零钱兑换)
描述：给定一个无重复数组nums，求构成目标数target使用最少的数字个数。数组中数字可以重复使用。
因为数字可以重复使用，不再是0-1背包问题，而是无界背包问题（也叫完全背包）。
分析：定义
F
(
i
)
F(i)
F(i) 表示组成目标值
i
i
i 所需要的最少数字数量, 那么
F
(
i
)
F(i)
F(i) 对应的状态转移方程为:
F
(
i
)
=
min
?
j
=
0..
n
?
1
F
(
i
?
c
j
)
+
1
F(i)=\min _{j=0 . . n-1} F\left(i-c_{j}\right)+1
F(i)=j=0..n?1min?F(i?cj?)+1
其中
c
j
c_{j}
cj? 表示下标为
j
j
j 的数字的值. 目标值
i
i
i 需要从状态
F
(
i
?
c
j
)
F(i-c_{j})
F(i?cj?) 转移过来, 再算上选取值
c
j
c_{j}
cj? 数量1的贡献. 由于要取最小值, 所以
F
(
i
)
F(i)
F(i) 为前面能转移过来的状态的最小值加上数量1.
public int coinChange(int[] coins, int amount) {
int max = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, max);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
