Coin Change 2 - Dynamic Programming Unbounded Knapsack - Leetcode 518 - Python

0:00 - Read the problem
2:25 - Brute Force Explained
5:57 - Memoization Explained
8:52 - Naive DP Explained
13:40 - Optimal Space DP Explained
18:15 - Memoization Code
20:10 - O(n*m) Space DP
22:20 - O(n) Space DP

leetcode 518

#unbounded #knapsack #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[NeetCode]

This one turned out pretty long, but I hope the timestamps are helpful. Also, the code for all 3 solutions is in the description. 😃

[zahaankhan]

i have it crazy that interviewers expect you to have never seen this problem and answer it in an hour.

[pritam]

From coin change to coin change 2 it's a big jump pretty big to be honest.. shit man

[yashbhandari]

Hey, just as a heads up you can do an O(n) space dp solution using just one array:

dp=[0]*(amount+1)
dp[0] = 1
for coin in coins:
for i in range(1, amount+1):
if i - coin >=0:
dp[i] += dp[i-coin]
return dp[-1]

[aakankshajaiswal]

Thankyou for explaining using diagram. It was very helpful in understanding the space optimized approach.
Below is my bottom up dp iterative solution in Python3:

dp = [1] + [0]*amount

for coin in coins:
for amount_sum in range(coin, amount + 1):
dp[amount_sum] += dp[amount_sum - coin]

return dp[-1]

[rafaelbnn]

4:00 another way to look at it is to see that ALL the solutions that have a 1 will be in the first branch. That way you don't need to check again in the branch that starts with 2

[abhishek.singh.chambial]

Explained perfectly

Just a minor tweak to use one array solution
just update in-place instead of copying.
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
cache = [0]*(amount + 1)
cache[0]=1
for coin in coins:
for index in range(amount+1):
if index-coin>=0:
cache[index] += cache[index-coin]
return cache[amount]

[edelweis]

Great explanation! the only input that I want to add is that for the recursive top-down solution, while it can produce the correct answer,
the more accurate code that faithfully follows the top-down solution logic should be starting condition for "dfs(0, amount)", then change the base case in dfs(i, a) with following code:
"if a == amount" -> "if a == 0"
"if a > amount" -> "if a < 0"
and change the general case code as follows:
"cache[(i, a)] = dfs(i, a + coins[i]) + dfs(i + 1, a)" -> "cache[(i, a)] = dfs(i, a - coins[i]) + dfs(i + 1, a)"

The complete code is as follows:
class Solution(object):
def change(self, amount, coins):
"""
:type amount: int
:type coins: List[int]
:rtype: int
"""
cache = {}

def dfs(i, a):
if a == 0:
return 1
if a < 0:
return 0
if i == len(coins):
return 0
if (i, a) in cache:
return cache[(i, a)]

cache[(i, a)] = dfs(i, a - coins[i]) + dfs(i + 1, a)
return cache[(i, a)]

return dfs(0, amount)

the reason why we start with dfs(0, amount) is because in top down approach, we start with the final result value then slowly build our solution from the value amount to value 0(base case)

[mangalegends]

Thanks for the video! I had to draw out the recursion tree of your solution to really understand it. Definitely a more challenging problem

[jinny]

Thanks for the video! Could you also cover 'Minimum Cost For Tickets' which is one of DP problems chosen from you?

[DJ-bopz]

Very nice explanation. But I would like to suggest you (from a pedagogical point of view), that it would be better if you had the amounts in the ascending order (left = 0 to right = 5) instead of the other way around, as l2r is the way most people think about arrays.

[prashumagnusthefirst]

tbh to come up with recursive + memo was not that hard, but I kinda struggled to think this bottom up solu. He explained it well. Thanks

[ztluo]

The code and the graph you draw is reversed direction, was hard to figure out already

[samuelrobert]

If you start the inner loop from the range coin..amount, you can get rid of the if statement as it's guarenteed that (i - coin) will not be negative.

dp=[0]*(amount+1)
dp[0] = 1
for coin in coins:
for i in range(coin, amount+1):
dp[i] += dp[i-coin]
return dp[-1]

[DatascienceConcepts]

Great explanation!
You can further improve the space complexity (O(n)) by:
#might need to do coins.sort()
dp=[0]*(amount+1)
dp[0]=1

for coin in coins:
for value in range(coin, amount+1):
dp[value]+=dp[value-coin]
return dp[-1]

[ChetanAnnam]

Coming up with the code for the recursive way was the hardest part 😬

[sekirandahamza]

I fail to understand the table that is introduced at 8:05 .

[lubdhakmahapatra]

# y axis = coin values decrementing from left to right
# x axis = amount incrementing from top to bottom

# [1, 1, 1, 1] => [1, 1, 1, 1]
# [0, 0, 0, 0] => [1, 0, 0, 0]
# [0, 0, 0, 0] => [2, 1, 0, 0]
# [0, 0, 0, 0] => [2, 0, 0, 0]
# [0, 0, 0, 0] => [3, 1, 0, 0]
# [0, 0, 0, 0] => [4, 1, 1, 0]

for amount = 5 and coins = [1, 2, 5]

[errorbool]

class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [1] + [0] * amount

for c in coins:
for i in range(c, amount + 1):
dp[i] += dp[i - c]
return dp[-1]

[varcel]

"And this path, will never have any(one)" 4:05😢