Ошибка рекурсии сверху вниз и снизу вверх - PullRequest
Новая
       25

Ошибка рекурсии сверху вниз и снизу вверх

0 голосов
/ 22 сентября 2019

Я работал над https://leetcode.com/problems/coin-change/, Я написал рекурсию как сверху вниз, так и снизу вверх.Потратил немало времени, пытаясь понять, почему не работает нисходящая версия.Но я не мог понять какие-либо идеи? 

# 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

Вверх-версия, которую я написал, прекрасно работает.Я не вижу разницы между тем, что раньше не работало. 

# 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
...