leetcode-go/leetcode/medium/518.coin-change-2.go

func change(amount int, coins []int) int {
	dp := make([]int, amount+1)
	dp[0] = 1
	for _, c := range coins { // dp[i+c] += dp[i]
		for i := 0; i <= amount-c; i++ {
			dp[i+c] += dp[i]
		}
	}
	return dp[amount]
}

type pair struct {
	_1 int
	_2 int
}

func changeDFS(amount int, coins []int) int { // Memory search
	m := make(map[pair]int)
	return dfs(amount, coins, 0, m)
}

func dfs(amount int, coins []int, i int, m map[pair]int) (sum int) {
	if amount == 0 {
		return 1
	} else if len(coins) == i {
		return 0
	} else if val, ok := m[pair{amount, i}]; ok {
		return val
	}
	for c := 0; c <= amount; c += coins[i] {
		sum += dfs(amount-c, coins, i+1, m)
	}
	m[pair{amount, i}] = sum
	return
}