Re: [閒聊] 每日LeetCode

https://leetcode.com/problems/coin-change-ii/description/ 518. Coin Change II 給你一個數字amount 和不同種類的硬幣 coins[] 價值分別為coins[i]，求出 共有幾種方式可以把硬幣湊到恰好為 amount 價值，如果無法湊到返回0。 Example 1: Input: amount = 5, coins = [1,2,5] Output: 4 Explanation: there are four ways to make up the amount: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 Example 2: Input: amount = 3, coins = [2] Output: 0 Explanation: the amount of 3 cannot be made up just with coins of 2. Example 3: Input: amount = 10, coins = [10] Output: 1 思路： 1.選或不選的所有組合數基本上就是dp，如果硬幣 i 可以組成 amount，那就表示 存在一種組合價值恰好為 amount - coins[i]，我們只要把前面的組合加總累計 即可。 2.因為題目是要求組合，對 amount = 3 來說 [1,2] 和 [2,1] 算是同一種，所以 這題要用硬幣去循環（當前硬幣拿或不拿）而不是用金錢。 Java Code： ------------------------------------------------------ class Solution { public int change(int amount, int[] coins) { int[] dp = new int[amount + 1]; dp[0] = 1; for (int coin : coins) { for (int i = 1; i <= amount; i++) { if (i - coin < 0) continue; dp[i] += dp[i - coin]; } } return dp[amount]; } } ------------------------------------------------------ -- https://i.imgur.com/bFRiqA3.jpg --
※ 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1691743457.A.901.html

推 twosheep0603: 大師 08/11 16:51