Leetcode 322. Coin Change (python+cpp)

题目

解法1：recursion + memorization

这是很经典的完全背包问题。还是跟其他背包问题一样，从recursion的做法开始，也就是所谓的top down approach。要理解这个top down就看看下面这张图就行。

从图里可以看出，这边problem和subproblem的关系是这样的，F(S) = F(S-coin)+1,只要注意对recursion block的返回条件即可，具体如下：

• recursion的时候传的参数为remain，代表剩下需要组成的sum
• 若remain<0,代表当前路径不符合要求，返回一个无穷大值
• 若remain=0，则返回0，代表当前路径符合要求并且已经结束
• 否则的话，向下探索当前remain减去所有可能的coin的subproblem
• 通过上面的图我们可以发现，很多subproblem会被重复计算，为了节省时间，通过一个字典来储存已经得到的sub problem的解

python代码如下：

class Solution:def coinChange(self, coins: List[int], amount: int) -> intdef dfs(remain):if remain<0:return float('inf')if remain == 0:return 0if remain in memo:return memo[remain]memo[remain] = 1+min([dfs(remain-coin) for coin in coins])return memo[remain]memo = {
    }ans = dfs(amount)if ans == float('inf'):return -1return ans

时间复杂度：O(S*n),S代表amount, n代表coin的数量。由于没有重复计算，所以每个amount的subproblem会对每个coin尝试一次
空间复杂度：O(S),由memo字典消耗

解法2：动态规划

由上面的分析可以知道，每个问题可以被分为sub problem，所以说用动态规划来解当然是首选，而状态转移方程就是dp[i] = min(dp[i],dp[i-coin]+1) if coin<=i for all coins,为了更清楚地理解这个动态规划的过程，我用表格来推一下最简单的[1,2,5]和amount=11的情况。
python代码如下：

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:dp = [float('inf')] * (amount + 1)dp[0] = 0for coin in coins:for x in range(coin, amount + 1):dp[x] = min(dp[x], dp[x - coin] + 1)return dp[amount] if dp[amount] != float('inf') else -1 

而其实调换两个循环的顺序在这边也完全是一样的，如下：

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:dp = [0]+[float('inf')]*amountfor i in range(1,amount+1):for coin in coins:if i>=coin:dp[i] = min(dp[i],dp[i-coin]+1)if dp[-1] == float('inf'):return -1return dp[-1]

时间复杂度和空间复杂度都与recursion解法一致