Problem #15

Problem link
Solution:

package main

var arr [][]uint64

func main() {
    arr = make([][]uint64, 21)
    for i := range arr {
        arr[i] = make([]uint64, 21)
        for j := range arr[i] {
            arr[i][j] = uint64(0)
        }
    }
    arr[20][20] = uint64(1)
    println(noOfRoutes(0, 0))
}

func noOfRoutes(i, j int) uint64 {
    if arr[i][j] != uint64(0) {
        return arr[i][j]
    }
    var result uint64
    if i < 20 && j < 20 {
        result = noOfRoutes(i+1, j) + noOfRoutes(i, j+1)
    } else if i < 20 && j == 20 {
        result = noOfRoutes(i+1, j)
    } else {
        result = noOfRoutes(i, j+1)
    }
    arr[i][j] = result
    return result
}

Result: 137846528820
Time: 0m0.003s

Problem #31

Problem link
Solution:

package main

var total int
var coins []int

func main() {
    total, coins = 200, []int{1, 2, 5, 10, 20, 50, 100, 200}
    println(count(total, len(coins)))
}

func count(n, m int) int {
    if n == 0 {
        return 1
    } else if n < 0 {
        return 0
    } else if m <= 0 && n >= 1 {
        return 0
    }
    return count(n, m-1) + count(n-coins[m-1], m)
}

Result: 73682
Time: 0m0.094s