Coins solutions

caching.go

package main

import "fmt"

func main() {
	fmt.Printf("%d\n", iter(36, []int{25, 10, 5, 1})) // descending order, reverse of naive.
}

type Cache map[string]int

func (c Cache) Put(n int, coins []int, v int) {
	c[fmt.Sprintf("%d %v", n, coins)] = v	
//	fmt.Println("put")
}

func (c Cache) Get(n int, coins []int) (int, bool) {
	v, ok := c[fmt.Sprintf("%d %v", n, coins)]	
//	if ok {	
//		fmt.Printf("hit (%d, %v)\n", n, coins)
//	} else {	
//		fmt.Printf("miss(%d, %v)\n", n, coins)
//	}
	return v, ok
}

var cache = make(Cache)

func iter(n int, coins []int) int {
	if n == 0 {
		return 1	
	}
	if v, ok := cache.Get(n, coins); ok {	
		return v
	}
	if len(coins) == 1 {	
		if n%coins[0] == 0 {		
			cache.Put(n, coins, 1)	
			return 1
		} else {		
			cache.Put(n, coins, 0)	
			return 0
		}
	}	

	c := coins[0]	
	accum := 0
	for m:=n; m>=0; m -=c {	
		accum += iter(m, coins[1:])
	}	
	cache.Put(n, coins, accum)
	return accum
}

naive.go

package main

import "fmt"

func main() {
	fmt.Printf("%d\n", iter(10, []int{1, 5, 10, 25}))
}

type Combo []int
type ComboSet map[string]Combo

func (cs ComboSet) Add(c Combo) {
	cs[fmt.Sprintf("%v", c)] = c
}

func (cs ComboSet) Elems() *[]Combo {
	out := make([]Combo, len(cs))

	i:=0
	for _, c := range cs {
		out[i] = c
		i++
	}
		
	return &out
}

func iter(n int, coins []int) int {
	nCoin := len(coins)
	cache := make([]ComboSet, n+1)
	for i:=0; i<=n; i++ {
		cache[i] = make(ComboSet)
		if i == 0 {
			cache[i].Add(make(Combo, nCoin))
			continue
		}
		for j, c := range coins {
			if c > i {
				break
			}
			for _, way := range *cache[i-c].Elems() {
				combo := make(Combo, nCoin)
				copy(combo, way)
				combo[j]++
				cache[i].Add(combo)
			}
		}
	}
	return len(cache[n])
}