Posts Algorithms - Dynamic Programming
Post
Cancel

Algorithms - Dynamic Programming

Introduction

Dynamic programming, or DP, is a simple yet versatile algorithmic strategy that can be used to yield fast polynomial solutions to problems. The key concept behind the method is finding overlapping subproblems, the answers to which we can store to build up our solution. What’s an overlapping subproblem? Let’s see the most common example, calculating Fibonacci numbers.

From the above visual, and simply from the definition of the series, it’s clear that the subproblems are simply the corresponding previous Fibonacci numbers. We can also see that these subproblems overlap. If we used a simple recursive approach, we would have to calculate f(2) twice, f(1) four times, and so on.

To avoid excess computation, we store the results of these subproblems (the nth Fibonacci numbers) in an array as we calculate them. Our (simplified) solution then becomes:

1
2
3
4
5
def nth_fib(n):
  fib_nums = [0, 1, 1]
  for i in range(3, n+1):
    fib_nums.append(fib_nums[i-1]+fib_nums[i-2])
  return fib_nums[n]

More Examples

Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s.

As always in DP problems, we need to find out what the overlapping subproblem is. Let’s say our string is AABCCDCCB, and the corresponding longest palindromic substring is BCCDCCB. What subproblem do we solve to figure out that BCCDCCB is a palindrome? Well, the leftmost and rightmost digits must be the same, and the string without these digits must be a palindrome. Repeating the same process, we get to D, our smallest subproblem and palindrome.

Knowing the subproblem, the solution is straightforward. We create a 2D array (start and end index of substring) representing whether each substring is a palindrome. We can start by marking all single character substrings as palindromes, and work our way up using the rules we defined earlier.

Here’s what a solution may look like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def longestPalindrome(self, s: str) -> str:
       # Core idea: sub(i, j) is palindrome if i == j and sub(i+1, j-1) is palindrome
        if s == '':
            return ''
        n = len(s)
        pal_subs = [[False for _ in range(n)] for _ in range(n)]  # all possible substrings sub(i, j) = pal_subs[i][j]
        max_len = 0
        res = ''
        for pal_len in range(n):  # len of palindrome, starting at 0 (j - i)
            for i in range(n - pal_len):  # starting index
                j = i + pal_len  # end index
                pal_subs[i][j] = ((s[i] == s[j]) and ((pal_len <= 2) or pal_subs[i+1][j-1]))
                if pal_subs[i][j]:
                    if pal_len + 1 > max_len:
                        max_len = pal_len + 1
                        res = s[i : j+1]
        return res

Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,

1
2
3
Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Let’s find the subproblem. How would the length of the longest increasing subsequence (LIS) of [0, 3, 4, 0, 1, 5] relate to the LIS of, say, [0, 3, 4, 0, 1]? It would be the same if our new element, 5, didn’t contribute anything to the existing LIS (eg. be greater than the last element of this LIS), otherwise it would be the existing LIS length plus 1. But how can we tell if it’s contributing anything? Just storing the LIS at each subarray won’t tell us this.

Let’s reframe the problem to make things more clear. We define a new n-length array, denoting the length of LIS ending at each index in the original array. Our solution is the max of this array. Now, we can make use of the subproblem we defined earlier.

We can initialize this array with ones, because each the smallest LIS ending at a given element is just that element on its own, with a length of 1:

1
2
nums = [0, 3, 4, 0, 1, 5]
    -> [1, 1, 1, 1, 1, 1]

We begin with the subarray nums[:2], [0, 3]. 3 is greater than the LIS length ending at 0, so we increment the LIS length ending at 3 to 2:

1
2
nums = [0, 3, 4, 0, 1, 5]
    -> [1, 2, 1, 1, 1, 1]

We move on to the subarray nums[:3], [0, 3, 4]. 4 is greater than the LIS length ending at both 0 and 3, so it can contribute to both of these sequences. We increment the larger LIS length, 2, making the LIS length ending at 4 2+1=3:

1
2
nums = [0, 3, 4, 0, 1, 5]
    -> [1, 2, 3, 1, 1, 1]

Repeating this process, we end up with a final array of [1, 2, 3, 1, 2, 4]. Therefore, the length of our LIS is 4.

Here’s what a solution might look like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return n
        dp = [1 for i in range(n)] # LIS ending at each index
        for new_val_index in range(1, n):
            new_val = nums[new_val_index]
            largest_lis = 0
            for prev_val_index in range(new_val_index):
                prev_val = nums[prev_val_index]
                if prev_val < new_val:
                    lis = dp[prev_val_index]
                    largest_lis = lis if lis > largest_lis else largest_lis
            dp[new_val_index] = largest_lis + 1
        return max(dp)
This post is licensed under CC BY 4.0 by the author.