I worked at https://leetcode.com/problems/coin-change/ and wrote a top-down and bottom-up recursion. Spent a lot of time trying to figure out why the top-down version did not work. But I could not find any ideas?

```
# recursion: top-down
class Solution:
def coinChange(self, coins: List(int), amount: int) -> int:
def compute_num_coins(amount, num_coins_so_far):
if amount == 0:
return num_coins_so_far
if amount not in dp:
min_coins = float('inf')
for coin in coins:
if amount - coin >= 0:
num_coins = compute_num_coins(amount - coin, num_coins_so_far + 1)
min_coins = min(min_coins, num_coins)
dp(amount) = min_coins
return dp(amount)
dp = {}
min_coins = compute_num_coins(amount, 0)
return min_coins if min_coins != float('inf') else - 1
```

The bottom-up version I wrote works fine. I can not see the difference between the brands that do not work earlier.

```
# recursion: bottom-up
class Solution:
def coinChange(self, coins: List(int), amount: int) -> int:
def compute_num_coins(amount):
if amount == 0:
return 0
if amount not in dp:
min_coins = float('inf')
for coin in coins:
if amount - coin >= 0:
num_coins = compute_num_coins(amount - coin) + 1
min_coins = min(min_coins, num_coins)
dp(amount) = min_coins
return dp(amount)
dp = {}
min_coins = compute_num_coins(amount)
return min_coins if min_coins != float('inf') else - 1
```