CHANGE-MONEY

code for change money with golang

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
var memo map[int]int

func change(coins []int, kinds int, num int) int {
    if num == 0 {
        return 0
    }
    
    if cost, ok := memo[num]; ok {
        return cost
    }
    
    minCost := 0x7FFFFFFF
    for i := 0; i < kinds; i++ {
        if num - coins[i] >= 0 {
            curCost := change(coins, 3, num - coins[i])
            if curCost < minCost {
                minCost = curCost
            }    
        }
    }

    memo[num] = minCost + 1
    return minCost + 1
}

func main(){
    memo = make(map[int]int)
    coins := []int {1, 5, 10}
    fmt.Println(change(coins, 3, 7000))
}