Memoization and Tabulation in Dynamic Programming

Dynamic Programming (DP) is a method used to solve complex problems by breaking them down into simpler subproblems. It is particularly useful for optimizing recursive algorithms that have overlapping subproblems. There are two main techniques in DP: memoization and tabulation.

Memoization

Memoization is a top-down approach where the solution to each subproblem is stored in a data structure (usually an array or a hash table) so that it can be reused later without having to recompute it. This technique avoids the recomputation of the same subproblem multiple times.

Example: Fibonacci Sequence

The Fibonacci sequence is a classic example of a problem that benefits from memoization. Here's a Go implementation using memoization:

go
package main

import (
	"fmt"
)

// Memoization cache
var memo = map[int]int{}

// Fibonacci function with memoization
func fib(n int) int {
	if n <= 1 {
		return n
	}

	// Check if result is already computed
	if result, ok := memo[n]; ok {
		return result
	}

	// Compute and memoize the result
	memo[n] = fib(n-1) + fib(n-2)
	return memo[n]
}

func main() {
	n := 10
	fmt.Printf("Fibonacci(%d) = %d\n", n, fib(n))
}

Tabulation

Tabulation is a bottom-up approach where we solve all the subproblems starting from the smallest one and store the results in a table. This way, we build up the solution to the original problem by solving progressively larger subproblems.

Example: Fibonacci Sequence

The same Fibonacci sequence problem can be solved using tabulation:

go
package main

import (
	"fmt"
)

// Fibonacci function using tabulation
func fib(n int) int {
	if n <= 1 {
		return n
	}

	// Table to store Fibonacci numbers
	fibTable := make([]int, n+1)
	fibTable[0] = 0
	fibTable[1] = 1

	// Fill the table iteratively
	for i := 2; i <= n; i++ {
		fibTable[i] = fibTable[i-1] + fibTable[i-2]
	}

	return fibTable[n]
}

func main() {
	n := 10
	fmt.Printf("Fibonacci(%d) = %d\n", n, fib(n))
}

Comparison of Memoization and Tabulation

Memoization

• Approach: Top-down
• Data Structure: Uses a cache (usually a hash table or array)
• Recursive: Yes, typically implemented using recursive function calls
• Space Complexity: Potentially higher due to the recursion stack
• Use Case: Good for problems where recursion is a natural fit and subproblem results are reused frequently

Tabulation

• Approach: Bottom-up
• Data Structure: Uses a table (usually an array)
• Recursive: No, typically implemented using iterative loops
• Space Complexity: Usually lower as it does not use a recursion stack
• Use Case: Good for problems where you can build up the solution iteratively from smaller subproblems

Practical Examples

1. Longest Common Subsequence (LCS)

Memoization

go
package main

import (
	"fmt"
)

// LCS function with memoization
func lcsMemo(X, Y string) int {
	m := len(X)
	n := len(Y)
	memo := make([][]int, m+1)
	for i := range memo {
		memo[i] = make([]int, n+1)
	}

	var lcs func(int, int) int
	lcs = func(i, j int) int {
		if i == 0 || j == 0 {
			return 0
		}
		if memo[i][j] != 0 {
			return memo[i][j]
		}
		if X[i-1] == Y[j-1] {
			memo[i][j] = 1 + lcs(i-1, j-1)
		} else {
			memo[i][j] = max(lcs(i-1, j), lcs(i, j-1))
		}
		return memo[i][j]
	}

	return lcs(m, n)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	X := "AGGTAB"
	Y := "GXTXAYB"
	fmt.Printf("Length of LCS is %d\n", lcsMemo(X, Y))
}

Tabulation

go
package main

import (
	"fmt"
)

// LCS function using tabulation
func lcsTab(X, Y string) int {
	m := len(X)
	n := len(Y)
	L := make([][]int, m+1)
	for i := range L {
		L[i] = make([]int, n+1)
	}

	for i := 0; i <= m; i++ {
		for j := 0; j <= n; j++ {
			if i == 0 || j == 0 {
				L[i][j] = 0
			} else if X[i-1] == Y[j-1] {
				L[i][j] = L[i-1][j-1] + 1
			} else {
				L[i][j] = max(L[i-1][j], L[i][j-1])
			}
		}
	}

	return L[m][n]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	X := "AGGTAB"
	Y := "GXTXAYB"
	fmt.Printf("Length of LCS is %d\n", lcsTab(X, Y))
}

Conclusion

Memoization and tabulation are powerful techniques in dynamic programming that optimize recursive algorithms by storing and reusing results of subproblems. Memoization uses a top-down approach with recursion and caching, making it suitable for problems where recursion is natural. Tabulation, on the other hand, uses a bottom-up approach and iterative loops, which can be more efficient in terms of space complexity. Both techniques are essential tools for solving complex problems efficiently in Go.