#LeetCode:518. Coin Change 2

灆洢 2020-06-08 21:18:08

此題給予可用的硬幣以及要找錢的數量,想求得總共有幾種找零方法。

經典的找零錢問題,可以使用動態規劃(Dynamic Programming)的方式來解決,基本公式為排法(價格 i, 從第 1 種硬幣使用到第 j 種硬幣) = 排法(i - coin[j], j),利用這個公式進行建表即可得解。

Kotlin(176ms)

/*******************************************************
 * LeetCode 518. Coin Change 2                         *
 * Author: Maplewing [at] knightzone.studio            *
 * Version: 2020/06/08                                 *
 *******************************************************/
class Solution {
    fun change(amount: Int, coins: IntArray): Int {
        val changeCounts = IntArray(amount + 1) { 0 }
        changeCounts[0] = 1
        for (coin in coins) {
            for (i in 1..amount) {
                if (i - coin >= 0) {
                    changeCounts[i] += changeCounts[i - coin]
                }
            }
        }

        return changeCounts[amount]
    }
}

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料