算法练习 Leetcode 力扣 416. Partition Equal Subset Sum 使用0-1背包问题 2维dp模版的 Python 解法

问题描述

这题的最优解是使用Bottom up DP, 题目描述和详细解法可以参考这篇文章. 本文示范一下这题也可以直接使用这篇文章总结的0-1背包问题2维dp模版一字不改直接解

0-1背包问题2维度dp模版解法

Continue reading “算法练习 Leetcode 力扣 416. Partition Equal Subset Sum 使用0-1背包问题 2维dp模版的 Python 解法”

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

leetcode 322 coin change

题目在这里

自己想的答案,bottom up dp不太好想,从top down + cache开始,写了几次,每次简化一点,最终写成这样通过OJ。

Python 版本。

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        cache = {0:0}
        self.dfs(coins, amount, cache)
        return cache[amount]
        
    def dfs(self, coins, amount, cache):
        if amount in cache:
            return cache[amount]
        if amount == 0:
            return 0
        if amount < 0:
            return -1
        ans = float('inf')
        for coin in coins:
            rest_cnt = self.dfs(coins, amount - coin, cache)
            if rest_cnt != -1:
                ans = min(ans, rest_cnt + 1)
        if ans == float('inf'):
            cache[amount] = -1
            return -1
        
        cache[amount] = ans
        return ans 

为了更好理解算法,加了些log,记录dfs被call了几次和cache hit,和每个cache key被写入次数(使用cache和不用cache的情况。

用coins = [1, 2, 5]和amount = 11为例子

用了cache

dfs call: 34
cache hit: 15
key write times
1: 1
2: 1
3: 1
4: 1
5: 1
6: 1
7: 1
8: 1
9: 1
10: 1
11: 1

不用cache

dfs call: 928
cache hit: 0
key write times
1: 128
2: 75
3: 44
4: 26
5: 15
6: 9
7: 5
8: 3
9: 2
10: 1
11: 1

运行完后cache的内容如下

0: 0
1: 1
2: 1
3: 2
4: 2
5: 1
6: 2
7: 2
8: 3
9: 3
10: 2
11: 3

正是从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)。

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        dp = [0] * (amount + 1)
        for i in range(1, amount + 1):
            rest_min_cnt = -1
            for coin in coins:
                rest = i - coin
                if rest >= 0 and dp[rest] != -1:
                    if rest_min_cnt == -1:
                        rest_min_cnt = dp[rest]
                    else:
                        rest_min_cnt = min(rest_min_cnt, dp[rest])
            dp[i] = rest_min_cnt + 1 if rest_min_cnt != -1 else -1
            
        
        return dp[amount]                                    

过了多日以后自己重新想的Python写法, 看看是否已经内化并掌握. 对比上面, 做了一些改进, dp list init成全部-1, 代表一开始都不可能. dp[0]设成0, 代表一个coin都不取. 新解法省了rest_min_cnt一个变量.

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        dp = [-1] * (amount + 1)
        dp[0] = 0
        for i in range(1, amount + 1):
            for j in coins:
                k = i - j
                if k >= 0 and dp[k] != -1:
                    if dp[i] == -1:
                        dp[i] = dp[k] + 1
                    else:
                        dp[i] = min(dp[i], dp[k] + 1)
        return dp[amount]
        

Java版本的bottom up dp解法

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++) {
            int restMinCoins = -1;
            for (int coin : coins) {
                int remainder = i - coin;
                if (remainder >= 0 && dp[remainder] != -1) {
                    if (restMinCoins == -1) {
                        restMinCoins = dp[remainder];
                    } else {
                        restMinCoins = Math.min(restMinCoins, dp[remainder]);
                    }
                }
            }
            if (restMinCoins == -1) {
                dp[i] = -1;
            } else {
                dp[i] = restMinCoins + 1;
            }
        }
        return dp[amount];
    }
}