动态规划

算法练习 Leetcode 力扣 322. Coin Change 解法

leetcode 322 coin change

题目在这里。 自己想的答案,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