2023.08.11 Today's Challenge

fabichoi 2023. 8. 11. 23:45

https://leetcode.com/problems/coin-change-ii/

Coin Change II - LeetCode

Can you solve this real interview question? Coin Change II - You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the number of combinations that make up that

leetcode.com

완전 탐색으로 푸는 문제!

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        def solve(i, amount):
            if amount == 0:
                return 1
            if i == len(coins):
                return 0
            if memo[i][amount] != -1:
                return memo[i][amount]

            if coins[i] > amount:
                memo[i][amount] = solve(i+1, amount)
            else:
                memo[i][amount] = solve(i, amount-coins[i]) + solve(i+1, amount)
        
            return memo[i][amount]
        
        memo = [[-1] * (amount + 1) for _ in range(len(coins))]
        return solve(0, amount)