[Leetcode] 518. Coin Change 2

 

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Example 1:

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

Input: amount = 10, coins = [10] 
Output: 1

 

간단한 DP 문제이다. TopDown 방식과 bottomUp 방식 모두 풀수 있다.

 

// bottom up
public int change(int amount, int[] coins) {
		if (amount == 0) {
			return 1;
		}

		int n = coins.length;
		int [][] dp = new int[n][amount+1];

		// amount 가 0인 경우는, 그 자체로 0을 만든거라고 볼 수 있기 때문에 카운트가 1이다.
		for (int i = 0; i < n; i++) {
			dp[i][0] = 1;
		}


		for (int i = 0; i < n; i++) {
			for (int total = 1; total <= amount ; total++) {
				// 현재 동전을 넣지 않는 경우
				if (i > 0) {
					dp[i][total] = dp[i-1][total];
				}

				// 현재 동전을 넣는 경우
				if (total >= coins[i]) {
					dp[i][total] += dp[i][total-coins[i]];
				}
			}
		}

		return dp[n-1][amount];
	}

// top-down
public int change(int amount, int[] coins) {
		Integer [][] dp = new Integer[coins.length][amount+1];
		return solve(dp, amount, coins, 0);
	}

	private int solve(Integer[][] dp, int amount, int[] coins, int i) {
		if (amount == 0) {
			return 1;
		} else if (i >= coins.length) {
			return 0;
		}

		if (dp[i][amount] != null) {
			return dp[i][amount];
		}

		int count = 0;

		// 현재 coin 을 넣는 경우
		if (amount - coins[i] >= 0) {
			count += solve(dp, amount-coins[i], coins, i);
		}

		// 현재 coin 을 넣지 않는 경우
		count += solve(dp, amount, coins, i+1);

		return dp[i][amount] = count;
	}