How do I implement dynamic programming patterns in Go?

Dynamic programming is a powerful method for solving complex problems by breaking them down into simpler subproblems. It is often used in optimization problems where a solution can be constructed efficiently using previously computed results.

Implementing Dynamic Programming in Go

In Go, you can implement dynamic programming patterns using either memoization or tabulation. Below are examples of both approaches using the Fibonacci sequence as a typical dynamic programming problem.

Example 1: Memoization Approach

package main

import "fmt"

// Memoization function to calculate Fibonacci numbers
func fibMemo(n int, memo map[int]int) int {
    if n <= 1 {
        return n
    }
    if val, found := memo[n]; found {
        return val
    }
    memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo)
    return memo[n]
}

func main() {
    n := 10
    memo := make(map[int]int)
    result := fibMemo(n, memo)
    fmt.Println("Fibonacci of", n, "is", result)
}

Example 2: Tabulation Approach

package main

import "fmt"

// Tabulation function to calculate Fibonacci numbers
func fibTab(n int) int {
    if n <= 1 {
        return n
    }
    
    fibs := make([]int, n+1)
    fibs[0] = 0
    fibs[1] = 1
    
    for i := 2; i <= n; i++ {
        fibs[i] = fibs[i-1] + fibs[i-2]
    }
    return fibs[n]
}

func main() {
    n := 10
    result := fibTab(n)
    fmt.Println("Fibonacci of", n, "is", result)
}