Dynamic programming

Table of contents

  1. Introduction
  2. Fibonacci sequence
  3. Approximate string matching
  4. Longest increasing sequence
  5. References

Introduction

DP (dynamic programming) is an optimization method that involves caching earlier results in order to reduce later recomputations. It was developed by Richard Bellman in the 1950s [1, P. 273].

DP works well for problems that have a left to right ordering, e.g. character strings and integer sequences [1, P. 274].

There are three steps to solving a problem with DP:

  1. Formulate the answer as a recursive algorithm or recurrence relation.
  2. Show that the number of different parameter values your recurrence takes is bounded by a polynomial.
  3. Specify the order for the recurrence so that the partial results are available to use.

[1, P. 289]

DP is a classic tradeof of space for time [1, P. 274].

Fibonacci sequence

A good example of dynamic programming is calculating the Fibonacci sequence.

The Fibonacci sequence is defined:

A naive approach would be to calculate the number recursively, using 1 and 0 as the base cases:

def fib(n):
  if n == 0:
    return 0
  if n == 1:
    return 1
  return fib(n - 1) + fib(n - 2)

This recursive approach has a time complexity of . You can see that fib is calculated for the same value multiple times by looking at the call tree:

Figure: The call tree of fib(4)

Using DP, you can reduce it to time complexity. Instead of recursively computing the number, each result is stored and used in future calculations:

def fib(n):
  dp = {}
  dp[0] = 0
  dp[1] = 1

  for i in range(2, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2]

  return dp[n]

Note: this approach can be improved further by storing results in two single variables.

Approximate string matching

Approximate string matching is the problem of matching strings by their edit distance. That is, comparing strings by the number of operations are required to transform one string to another.

A simple set of operations include:

  • Substitution: Replace a single character in string with a different character.
  • Insertion: Insert a single character into string .
  • Deletion: Delete a single character from string .

[1, P. 280]

Operations may have different associated costs depending on the characters involved. For example, replacing a with s might have lower cost than replacing a with h, because on a keyboard s is closer to a than h is to a.

If the problem is just to count the minimum number of operations required to transform a string, then each operation is given a cost of 1.

The edit distance can be calculated by building a x matrix of the cost to transform string to string at each position . Where and .

Figure: A complete edit distance matrix

At point you need to know the minimum cost operation to make equal . If results for the positions , , have already been computed, you can calculate the operation costs as follows:

  • Replace is if . Otherwise, the cost is .
  • Insertion is , because has been advanced but has not.
  • Deletion is , because has been advanced, but has not.

The first step is to calculate the cost from an empty string to string and an empty string to string . This will always be , where is the length of the substring, because an empty string requires insertions to equal a substring of length .

Figure: The initial edit distance matrix

After calculating the base costs, you loop over each empty matrix position and calculate the cost by following the rules listed above. The value at matrix position is the final edit distance.

def min_distance(word1, word2):
    n = len(word1)
    m = len(word2)

    # Build m x n matrix
    d = [[0] * (m + 1) for _ in range(n + 1)]

    # Initial costs of operations
    for i in range(n + 1):
        d[i][0] = i
    for j in range(m + 1):
        d[0][j] = j

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            replace = d[i - 1][j - 1]
            delete = d[i][j - 1] + 1
            insert = d[i - 1][j] + 1
            if word1[i - 1] != word2[j - 1]:
                replace += 1
            d[i][j] = min(replace, delete, insert)

    return d[i][j]

For a detailed explanation, see this MIT lecture on calculating edit distance.

Longest increasing sequence

The longest increasing sequence is the longest monotonically increasing subsequence within a sequence of numbers [1, P. 290].

Note: here a sequence is different from a run. Neighbors don’t have to be next to each other in a sequence.

In the sequence , there are 8 monotonically increasing subsequences with length 5, for example .

To determine the longest length of a subsequence at position , you need to know:

  1. The length of the longest increasing sequence in .
  2. The length of the longest increasing sequence that will extend.

[1, P. 290]

Define to be the length of the longest sequence ending with . The longest increasing subsequence at is formed by appending to the longest subsequence in where is less than :

[1, P. 290]

This can be implemented in by calculating the longest subsequence of each previous value:

def lengthOfLIS(self, nums):
    n = len(nums)
    dp = {}

    longest = 0

    for i in range(n):
        l = 0
        for j in range(i):
            if nums[i] > nums[j]:
                l = max(l, dp[j])
            j -= 1
        l += 1
        longest = max(longest, l)
        dp[i] = l

    return longest

Note: there are improved solutions to this problem. For example, see this Leetcode longest increasing substring solution.

References

  1. [1] S. Skiena, The Algorithm Design Manual, 2nd ed. Springer, 2008.