0518.go

// Source: https://leetcode.com/problems/coin-change-2
// Title: Coin Change 2
// Difficulty: Medium
// Author: Mu Yang <http://muyang.pro>

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 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 amount. If that amount of money cannot be made up by any combination of the coins, return 0.
//
// You may assume that you have an infinite number of each kind of coin.
//
// The answer is guaranteed to fit into a signed 32-bit integer.
//
// 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
//
// Constraints:
//
//   1 <= coins.length <= 300
//   1 <= coins[i] <= 5000
//   All the values of coins are unique.
//   0 <= amount <= 5000
//
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

package main

import (
	"sort"
)

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// Use 2D DP
// dp[i][j] = number of combinations (using only coins[0]...coin[i-1]) for amount=j
func change(amount int, coins []int) int {
	sort.Ints(coins)

	n := len(coins)

	dp := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, amount+1)
	}

	for i := 1; i <= n; i++ {
		coin := coins[i-1]
		dp[i][0] = 1
		for j := 1; j <= amount; j++ {
			dp[i][j] = dp[i-1][j]
			if coin <= j {
				dp[i][j] += dp[i][j-coin]
			}
		}
	}

	return dp[n][amount]
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// Use 1D DP
func change2(amount int, coins []int) int {
	sort.Ints(coins)

	dp := make([]int, amount+1)
	dp[0] = 1

	for _, coin := range coins {
		for i := coin; i <= amount; i++ {
			dp[i] += dp[i-coin]
		}
	}

	return dp[amount]
}