背包

題目在這裡。 自己想的答案，bottom up dp不太好想，從top down + cache開始，寫了幾次，每次簡化一點，最終寫成這樣通過OJ。 Python 版本。 為了更好理解算法，加了些log，記錄dfs被call了幾次和cache hit，和每個cache key被寫入次數（使用cache和不用cache的情況。 用coins = [1, 2, 5]和amount = 11為例子 用了cache 不用cache 運行完後cache的內容如下 正是從0到11每個amount的最少硬幣數。從此出發，想到bottom up dp正是需要構建如上cache的內容。dp[0] = 0，amount是0，當然一個硬幣不用。dp[amount]就看amount – coin值是不是正，而且之前是否有非-1的值。當算到amount的時候，前面dp[0]到d][amount-coin]都算過了。對所有的coin值都算一遍，把所有dp[amount – coin]的非-1最小值找出來，加1，就是dp[amount]。時間複雜度為O(amount * len(coins))。空間為 O(amount)。 過了多日以後自己重新想的Python寫法, 看看是否已經內化並掌握. 對比上面, 做了一些改進, dp list…
Read more