凑硬币问题

迷南。 2022-10-27 13:54 275阅读 0赞 
  1. /** * 给出k中面值的硬币，每种硬币的数量无限，再给一个总金额amount，问最少需要几枚硬币凑出这个金额，如果凑不出，返回-1 * dp[i]定义：当目标金额为i时，至少需要dp[i]枚硬币凑出 */
  2. public class Coin { 
  4.     public static void main(String[] args) { 
  5.         int[] coins = new int[] { 1,3,5};
  6.         int amount = 11;
  7.         int res = calc(coins, amount);
  8.         System.out.println(res);
  9.     }
  11.     static int calc(int[] coins, int amount) { 
  12.         int[] dp = new int[amount + 1];
  13.         Arrays.fill(dp, amount + 1);
  14.         dp[0] = 0;
  15.         for (int i = 0; i < dp.length; i++) { 
  16.             for (int coin: coins) { 
  17.                 if (i - coin < 0) continue;
  18.                 //状态转移方程，
  19.                 //比较凑齐当前金额i需要的硬币和凑齐减去一个coin的金额i-coin所需要的硬币+1块硬币的数量，谁更小
  20.                 dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
  21.             }
  22.         }
  23.         return dp[amount];
  24.     }
  26. }

发表评论

表情：
评论列表 （有 0 条评论，275人围观）

还没有评论，来说两句吧...

相关阅读

    相关 凑零钱问题

    题目：给你k种面值的硬币，面值分别为 c1, c2 … ck，每种硬币的数量无限，再给一个总金额 amount，问你amount 最少需要几枚硬币凑出这个金额，如果不可能凑出，

    冷不防冷不防/ 0 赞/ 95 阅读

    相关 凑硬币问题

    / 给出k中面值的硬币，每种硬币的数量无限，再给一个总金额amount，问最少需要几枚硬币凑出这个金额，如果凑不出，返回-1 dp[i]定义：当目标金额为i时，至少

    迷南。迷南。/ 0 赞/ 276 阅读

    相关 动态规划凑硬币

    > 题目：几年教师节活动中，公司里为培训讲师提供了不同面值的饮料兑换券（每种面值数量不限），培训讲师可以领取兑换券去食堂兑换鲜榨果汁，要求兑换券和果汁必须等价，姜小虎想要兑换一

    Bertha 。Bertha 。/ 0 赞/ 293 阅读

    相关 动态规划 凑硬币问题

    凑硬币问题 假设有 1 元，3 元，5 元的硬币若干（无限），现在需要凑出 11 元，问如何组合才能使硬币的数量最少？ 用数组d来存储当前每个面值可以对应的合成的最小

    Dear 丶Dear 丶/ 0 赞/ 514 阅读