Common Dynamic Programming Problems

Dynamic programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems and solving each subproblem only once, storing the solutions to subproblems to avoid redundant work. Here, we'll discuss classic DP problems like the Knapsack problem, Longest Increasing Subsequence, and Matrix Chain Multiplication, including their implementations in Go.

1. Knapsack Problem

The Knapsack problem involves selecting items with given weights and values to maximize the total value without exceeding the weight capacity of the knapsack.

Problem Statement: Given weights and values of n items, and a knapsack with a capacity W, find the maximum value that can be put in the knapsack.

Implementation:

go
package main

import (
	"fmt"
)

// Knapsack function using dynamic programming
func knapsack(W int, wt []int, val []int, n int) int {
	// Create a 2D slice to store the maximum value that can be achieved with given weight and items
	K := make([][]int, n+1)
	for i := range K {
		K[i] = make([]int, W+1)
	}

	// Build the table K[][] in bottom-up manner
	for i := 0; i <= n; i++ {
		for w := 0; w <= W; w++ {
			if i == 0 || w == 0 {
				K[i][w] = 0
			} else if wt[i-1] <= w {
				K[i][w] = max(val[i-1]+K[i-1][w-wt[i-1]], K[i-1][w])
			} else {
				K[i][w] = K[i-1][w]
			}
		}
	}

	return K[n][W]
}

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

func main() {
	val := []int{60, 100, 120}
	wt := []int{10, 20, 30}
	W := 50
	n := len(val)
	fmt.Println("Maximum value in knapsack =", knapsack(W, wt, val, n))
}

2. Longest Increasing Subsequence (LIS)

The Longest Increasing Subsequence problem involves finding the longest subsequence in a sequence such that all elements of the subsequence are sorted in increasing order.

Problem Statement: Given an array of integers, find the length of the longest increasing subsequence.

Implementation:

go
package main

import (
	"fmt"
)

// LIS function using dynamic programming
func lis(arr []int) int {
	n := len(arr)
	lis := make([]int, n)

	// Initialize LIS values for all indexes
	for i := range lis {
		lis[i] = 1
	}

	// Compute optimized LIS values in bottom-up manner
	for i := 1; i < n; i++ {
		for j := 0; j < i; j++ {
			if arr[i] > arr[j] && lis[i] < lis[j]+1 {
				lis[i] = lis[j] + 1
			}
		}
	}

	// Find the maximum value in lis[]
	maxLis := 0
	for i := 0; i < n; i++ {
		if lis[i] > maxLis {
			maxLis = lis[i]
		}
	}

	return maxLis
}

func main() {
	arr := []int{10, 22, 9, 33, 21, 50, 41, 60}
	fmt.Println("Length of LIS =", lis(arr))
}

3. Matrix Chain Multiplication

The Matrix Chain Multiplication problem involves determining the most efficient way to multiply a given sequence of matrices.

Problem Statement: Given a sequence of matrices, find the most efficient way to multiply these matrices together. The problem is to find the minimum number of multiplications needed to multiply the chain.

Implementation:

go
package main

import (
	"fmt"
	"math"
)

// MatrixChainOrder function using dynamic programming
func matrixChainOrder(p []int, n int) int {
	// Create a 2D slice to store the minimum number of multiplications
	m := make([][]int, n)
	for i := range m {
		m[i] = make([]int, n)
	}

	// cost is zero when multiplying one matrix
	for i := 1; i < n; i++ {
		m[i][i] = 0
	}

	// l is chain length
	for l := 2; l < n; l++ {
		for i := 1; i < n-l+1; i++ {
			j := i + l - 1
			m[i][j] = math.MaxInt32
			for k := i; k <= j-1; k++ {
				// cost = cost/scalar multiplications
				q := m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
				if q < m[i][j] {
					m[i][j] = q
				}
			}
		}
	}

	return m[1][n-1]
}

func main() {
	arr := []int{1, 2, 3, 4}
	n := len(arr)
	fmt.Printf("Minimum number of multiplications is %d\n", matrixChainOrder(arr, n))
}

Summary

• Knapsack Problem: Solved using a 2D array to store the maximum value for different weights and item counts.
• Longest Increasing Subsequence: Utilizes a 1D array to keep track of the length of the longest subsequence ending at each element.
• Matrix Chain Multiplication: Uses a 2D array to store the minimum number of scalar multiplications required to multiply matrices from i to j.

Each of these problems demonstrates the power of dynamic programming in optimizing solutions for complex recursive problems by storing and reusing the results of subproblems.