本文主要是介绍零钱兑换——使用动态规划，求解——Java，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
322. 零钱兑换 - 力扣（LeetCode）
—— 凑成总金额的最少硬币个数
使用动态规划，二维数组缓存每种价值使用的硬币数，最后得到amount价值时最少的硬币数
0 1 2 3 4 5 --> 钱值
1 0 1 11 111 1111 11111
2 0 1 2 21 22 221
5 0 1 2 21 22 5
换成对于硬币数量后：
0 1 2 3 4 5 --> 钱值
1 0 1 2 3 4 5
2 0 1 1 2 2 3
5 0 1 1 2 2 1
结果即为 1
能凑成 --> 当前硬币面值比所要填充的钱值**小**时，需填充的硬币数是 1 加上钱值 - 硬币面值时的最少硬币数，该结果若比上一行小则使用该值，否则还是使用上一行的值
例如：第二行第三列的21，即一个2硬币和一个1硬币，硬币数为2，一个2硬币是因为，2 < 3,一个1硬币是因为3-2 = 1，在钱值为1时中去找硬币数最少的结果是1，
不能凑成 --> 当前硬币面值比所要填充的钱值**大**时，使用一个最大值，这里规定为amount+1,因为硬币数不可能超过amount，超过表示不能凑成，返回-1
例如：amount = 2,coins[] = {3}，想要用3面值的硬币凑成2是不可能的，返回-1
0 1 2 3
0 4 1 5
-1
结果返回，在最后一个硬币数，即dp[coins.length - 1][amount] 大于amount则返回-1，否则返回对应硬币数，就为最少硬币数。
最后对二维代码降维优化处理。
/*** 求凑成 amount 值的最少硬币数** @param amount* @param coins 硬币* @return 最少硬币数*/private int dpChange2(int amount, int[] coins) {int[][] dp = new int[coins.length][amount + 1]; //缓存使用的硬币数//第一行，使用 1 硬币for (int j = 1; j < amount + 1; j++) {if (coins[0] <= j) { //能放下dp[0][j] = 1 + dp[0][j - coins[0]];} else { //放不下dp[0][j] = amount + 1; //放一个最大值}}for (int i = 1; i < coins.length; i++) {for (int j = 0; j < amount + 1; j++) {int upCnt = dp[i - 1][j];if (j >= coins[i]) {dp[i][j] = Math.min(upCnt, 1 + dp[i][j - coins[i]]);} else {dp[i][j] = upCnt;}}}int res = dp[coins.length - 1][amount];return res >= amount + 1 ? -1 : res;}可优化的地方：
第一行硬币数初始化，换成填充为最大值amount+1，自然第一个数为0，因为钱值为0，凑成硬币数也为0。
换成一维数组后，else部分就不需要了
第二成for循环中，要在j >= coins[i]即钱值大于硬币面值时才计算最小硬币数，和不让j从该面值开始，if条件也不需要了
降维优化后的结果：
class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount + 1]; //缓存使用的硬币数//dp数组初始化Arrays.fill(dp, amount + 1);dp[0] = 0;//计算每种价值时的所需最少硬币数for (int coin : coins) for (int j = coin; j < amount + 1; j++) {dp[j] = Math.min(dp[j], 1 + dp[j - coin]);}return dp[amount] >= amount + 1 ? -1 : dp[amount];}}518. 零钱兑换 II - 力扣（LeetCode）
0 1 2 3 4 5 --> 钱值 1 1 1 11 111 1111 111112 1 1 11 111 1111 111111 2 21 211 211122 221 5 1 1 11 111 1111 111111 2 21 211 211122 2215结果：4 种0 1 2 3 4 5 --> 钱值 1 1 1 1 1 1 1 2 1 2 2 2 3 3 5 1 2 2 2 3 4 结果：4 种
解法与322类似，区别在于dp二维数组中，第一列的值要初始化为1，，记录的是有多少中凑法，
以第二行第4列为例：
1111 211 22
第一种凑法1111是上一行的的凑法，（一种），4 - 2 = 2, 使用面值2与第二列的凑法结合，2 和 11以及2 和 2，总共是上一行的凑法1加上这两种结果有3种，以此类推的到最终结果4
public static void main(String[] args) {System.out.println(new L_518().dpChange(5, new int[]{1, 2, 5}));
// System.out.println(new L_322().change(41, new int[]{25,10,5,1}));
// System.out.println(new L_518().dpChange2(3, new int[]{2}));
// System.out.println(new L_518().dpChange(1, new int[]{2}));
// System.out.println(new L_518().dpChange(8, new int[]{5, 2, 1}));}/*** 求凑成 amount 值有多少中凑法（动态规划-完全背包问题）降维优化** @param amount* @param coins 硬币* @return 最少硬币数*/private int dpChange(int amount, int[] coins) {int[] dp = new int[amount + 1]; //缓存使用的硬币数//初始化第一列的值为 1dp[0] = 1;for (int coin : coins)for (int j = coin; j < amount + 1; j++) {dp[j] += dp[j - coin];}return dp[amount];}/*** 求凑成 amount 值的最少硬币数 （动态规划-完全背包问题）** @param amount* @param coins 硬币* @return 最少硬币数*/private int dpChange2(int amount, int[] coins) {int[][] dp = new int[coins.length][amount + 1]; //缓存使用的硬币数//初始化第一列的值为 1for (int i = 0; i < dp.length; i++) {dp[i][0] = 1;}//第一行，使用 1 硬币for (int j = 1; j < amount + 1; j++) {if (coins[0] <= j) { //能放下dp[0][j] = dp[0][j - coins[0]];}}for (int i = 1; i < coins.length; i++) {for (int j = 0; j < amount + 1; j++) {int upCnt = dp[i - 1][j];if (j >= coins[i]) {dp[i][j] = upCnt + dp[i][j - coins[i]];} else {dp[i][j] = upCnt;}}}print(dp);return dp[coins.length - 1][amount];}降维优化：
/*** 求凑成 amount 值有多少中凑法（动态规划-完全背包问题）降维优化** @param amount* @param coins 硬币* @return 最少硬币数*/private int dpChange(int amount, int[] coins) {int[] dp = new int[amount + 1]; //缓存使用的硬币数//初始化第一列的值为 1dp[0] = 1;for (int coin : coins)for (int j = coin; j < amount + 1; j++) {dp[j] += dp[j - coin];}return dp[amount];}这篇关于零钱兑换——使用动态规划，求解——Java的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
