Dynamic Programming

Posted on by user

Dynamic programming (DP) is a method for solving a complex problem by breaking it down into simpler subproblems. It’s used in a variety of contexts in computer science and mathematics.

Here are some classic problems, besides the Subset Sum problem, that are often solved using dynamic programming:

  1. Fibonacci Sequence: Calculating the nth Fibonacci number efficiently using memoization or tabulation to avoid redundant calculations.
  2. 0/1 Knapsack Problem: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
  3. Longest Common Subsequence (LCS): Given two sequences, find the length of the longest subsequence present in both of them.
  4. Longest Increasing Subsequence: Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
  5. Matrix Chain Multiplication: Given a sequence of matrices, determine the most efficient way to multiply these matrices together.
  6. Coin Change Problem: Given a set of coin denominations and a total amount of money, find the minimum number of coins needed to make up that amount.
  7. Edit Distance (Levenshtein Distance): Given two strings, compute the minimum number of operations required to convert one string into the other, where an operation is an insertion, deletion, or substitution of a single character.
  8. Rod Cutting Problem: Given a rod of length n and a table of prices for i-length rods, find the optimal way to cut the rod into smaller rods to maximize profit.
  9. Maximum Subarray Problem: Finding the contiguous subarray within a one-dimensional array of numbers that has the largest sum.
  10. Word Break Problem: Given a non-empty string and a dictionary containing a list of non-empty words, determine if the string can be segmented into a space-separated sequence of one or more dictionary words.
  11. Travelling Salesman Problem (TSP): Given a list of cities and the distances between each pair of cities, find the shortest possible route that visits each city exactly once and returns to the origin city.
  12. Palindrome Partitioning: Given a string, partition it such that every substring of the partition is a palindrome. Determine the minimum number of cuts needed.

These problems showcase the versatility of dynamic programming in tackling a wide range of problems involving optimization, combinatorics, and computational geometry. Each problem typically has a unique structure and properties that DP can exploit to find an efficient solution.

The “Subset Sum” problem is a classic problem in computer science and combinatorics. The problem statement is as follows:

Given a set of integers and a target sum, determine if there is a subset of the given set with a sum equal to the target sum.

For example, given the set ([3, 34, 4, 12, 5, 2]) and the target sum (9), one possible subset that adds up to (9) is ([4, 5]).

Solving Subset Sum Problem in Golang

To solve the Subset Sum problem, a common approach is to use dynamic programming. Here is the Go code implementing a solution:

package main

import (
    "fmt"
)

// SubsetSum checks if there's a subset with sum equal to the given sum in the array.
func SubsetSum(arr []int, sum int) bool {
    n := len(arr)
    dp := make([][]bool, n+1)

    // Initialize DP array
    for i := range dp {
        dp[i] = make([]bool, sum+1)
    }

    // Sum 0 can always be achieved with an empty subset
    for i := 0; i <= n; i++ {
        dp[i][0] = true
    }

    // Fill the DP array
    for i := 1; i <= n; i++ {
        for j := 1; j <= sum; j++ {
            if j < arr[i-1] {
                dp[i][j] = dp[i-1][j]
            } else {
                dp[i][j] = dp[i-1][j] || dp[i-1][j-arr[i-1]]
            }
        }
    }

    return dp[n][sum]
}

func main() {
    arr := []int{3, 34, 4, 12, 5, 2}
    sum := 9
    if SubsetSum(arr, sum) {
        fmt.Println("Found a subset with given sum")
    } else {
        fmt.Println("No subset with given sum")
    }
}

How the Code Works:

  1. DP Array Initialization: A 2D DP array dp is created, where dp[i][j] will be true if there is a subset of the first i elements of arr that adds up to j.
  2. Base Case: We initialize dp[i][0] = true for all i, because a sum of 0 can always be achieved with an empty subset.
  3. Filling the DP Array:
    • If the current element is greater than the current sum j, we just carry forward the value from the previous row (dp[i-1][j]).
    • Otherwise, we check if any of the two conditions is true: either the sum j was already achievable without the current element (dp[i-1][j]) or it is achievable with the current element (dp[i-1][j-arr[i-1]]).
  4. Result: The value at dp[n][sum] gives the final answer, whether a subset with the given sum exists or not.

Complexity:

  • Time Complexity: (O(n \times \text{sum})), where n is the number of elements in the set and sum is the target sum.
  • Space Complexity: (O(n \times \text{sum})), for the 2D DP array.

This code effectively solves the Subset Sum problem using dynamic programming, a technique commonly used for optimization problems involving a choice under constraints.

Reference:
1. https://zhuanlan.zhihu.com/p/37822898

1