Go dynamic programming

can_sum_test.go

package main

import (
	"fmt"
	"testing"
)

type memo = map[int]bool

func mCanSum(target int, numbers []int, m memo) bool {
	if target <= 0 {
		return target == 0
	}
	if v, ok := m[target]; ok {
		return v
	}
	if m == nil {
		m = make(memo)
	}

	for _, n := range numbers {
		if mCanSum(target-n, numbers, m) {
			m[target] = true
			return true
		}
	}

	m[target] = false
	return false
}

func CanSum(target int, numbers []int) bool {
	return mCanSum(target, numbers, nil)
}

func TestCanSum(t *testing.T) {
	scenarios := []struct {
		target   int
		numbers  []int
		expected bool
	}{
		{7, []int{2, 3}, true},
		{13, []int{5, 3, 4, 7}, true},
		{7, []int{2, 4}, false},
		{8, []int{2, 3, 5}, true},
		{300, []int{7, 14}, false},
	}

	for _, s := range scenarios {
		name := fmt.Sprintf("CanSum(%d,%v)", s.target, s.numbers)
		t.Run(name, func(t *testing.T) {
			got := CanSum(s.target, s.numbers)
			if got != s.expected {
				t.Errorf("expected %t, got %t", s.expected, got)
			}
		})
	}
}

fib_test.go

package main

import (
	"fmt"
	"testing"
)

func mFib(n uint, m map[uint]uint) uint {
	if n <= 2 {
		return 1
	}

	if m == nil {
		m = make(map[uint]uint)
	}

	if v, ok := m[n]; ok {
		return v
	}

	v := mFib(n-1, m) + mFib(n-2, m)
	m[n] = v
	return v
}

func Fib(n uint) uint {
	return mFib(n, nil)
}

func TestFib(t *testing.T) {
	scenarios := []struct {
		n uint
		v uint
	}{
		{1, 1},
		{2, 1},
		{50, 12586269025},
		{90, 2880067194370816120},
	}

	for _, s := range scenarios {
		name := fmt.Sprintf("Fib(%d)", s.n)
		t.Run(name, func(t *testing.T) {
			v := Fib(s.n)
			if v != s.v {
				t.Errorf("expected %d, got %d", s.v, v)
			}
		})
	}
}

grid_paths_test.go

package main

import (
	"fmt"
	"testing"
)

type key struct {
	f, s uint
}
type memo = map[key]uint

func mGridPaths(x, y uint, m memo) uint {
	if x == 0 || y == 0 {
		return 0
	}
	if x == 1 && y == 1 {
		return 1
	}
	if m == nil {
		m = make(memo)
	}

	var k key
	// since mGridPaths(a, b) == mGridPaths(b, a), we make sure that the key covers both cases
	if x < y {
		k = key{x, y}
	} else {
		k = key{y, x}
	}

	if v, ok := m[k]; ok {
		return v
	}

	v := mGridPaths(x-1, y, m) + mGridPaths(x, y-1, m)
	m[k] = v
	return v
}

func GridPaths(x, y uint) uint {
	return mGridPaths(x, y, nil)
}

func TestGridPaths(t *testing.T) {
	scenarios := []struct {
		x, y uint
		v    uint
	}{
		{0, 0, 0},
		{1, 1, 1},
		{2, 3, 3},
		{3, 2, 3},
		{3, 3, 6},
		{18, 18, 2333606220},
	}

	for _, s := range scenarios {
		name := fmt.Sprintf("GridPaths(%d,%d)", s.x, s.y)
		t.Run(name, func(t *testing.T) {
			v := GridPaths(s.x, s.y)
			if v != s.v {
				t.Errorf("expected %d, got %d", s.v, v)
			}
		})
	}
}