Learn to Code via Tutorials on Repl.it!

← Back to all posts
DP #2: Basic Dynamic Programming Problems
h
MrEconomical (2197)

IF YOU HAVEN'T ALREADY SEEN THE FIRST TUTORIAL IN THE SERIES, CHECK IT OUT HERE: https://repl.it/talk/learn/DP-1-Introduction-to-Dynamic-Programming/31658

Common Dynamic Programming Problems

In the previous tutorial, we explored the concept of dynamic programming and how it can be used to optimize recursion. Unlike the recursive top-down structure, we solve the smaller subproblems then use these small solutions to build up to our final answer. In this tutorial, we will explore some very basic dynamic programming problems and see how it is actually implemented. NOTE: The solutions to the problems will be written in JavaScript, but you don't need to know JavaScript to understand the tutorial!

Longest Increasing Subsequence (LIS)

This is one of the most classic dynamic programming problems out there and can be stated very simply: given an array of numbers, find the longest increasing subsequence of the array. Here's an example:

Let's say our array of numbers is [2, 8, 3, 1, 6, 5, 9]. The longest increasing subsequence of the array is the longest set of numbers from the array, in order, that form an increasing sequence. In this case, [1, 5, 9] is one such subsequence, but not the longest. The solution is the subsequence [2, 3, 5, 9] and thus our answer is 4.

A first thought to solve this problem would be the brute force approach. First, start with a variable that stores the current maximum value. Recursively find all the subsets in the array and then check to see if they are increasing. If a subset is indeed increasing, keep track of the length and update our current maximum. At the end of this process, our maximum value will be the longest increasing subsequence. This algorithm would look something like this (I won't go into the exact details):

array = [2, 8, 3, 1, 6, 5, 9]

max = 0
(for each subset of array)
    if (subset increasing)
        max = maximum(max, (length of subset))

This solution would work, however it is incredibly slow, running in O(2^n) time. This is exponential, meaning that even adding one number to the array would double the time it takes for your algorithm to run!

A key observation about this problem that lets us optimize our solution is that for any number in the array, the length of the LIS up to that point is the maximum of the length of the LISes of the numbers before that point, in addition to the current number if it is greater than the previous value.

What exactly does this mean? Well, let's look again at our example [2, 8, 3, 1, 6, 5, 9]. The length of the LIS at the 5th element, 6, would be the maximum of the length of the LIS ending at 2, the length of the LIS ending at 3, or the length of the LIS ending at 1 plus one (the current value, 6). In this case, the (maximum of 1 2 1) + 1, being 2 + 1 = 3. What have we done here? We have looked back at our previously calculated solutions for the previous elements, then if we can add 6 to those solutions and still be a valid increasing subsequence, we do so.

We can store the previously calculated solution in a separate array, then advance along this array and look back at all our previous values and find the maximum valid value to add our current number to. In this way, the dynamic programming solution to this problem is able to use the previously calculated solutions and runs in O(N^2) time, a huge improvement to our old O(2^N). Here is a simple JavaScript implementation:

// data

array = [2, 8, 3, 1, 6, 5, 9] // our array of values
sequence_values = [1, 1, 1, 1, 1, 1, 1] // length of LIS at a number is at minimum itself (1)

// iterate through array

for (let elem = 0; elem < array.length; elem ++) {
    // go back to check previous LIS solutions
    for (let prev = elem; prev >= 0; prev --) {
        // check if we can add current element and still be increasing
        if (array[prev] < array[elem]) {
            // take maximum of "in progress" current value and our potential subsequence
            sequence_values[elem] = Math.max(sequence_values[elem], sequence_values[prev] + 1)
        }
    }
}

// our solution is last element

console.log("LIS is:", sequence_values[array.length - 1])

Run the solution here: https://repl.it/@MrEconomical/dp-lis

Path Walking

Consider for a second that you are at the top left corner of a square grid of values. You must walk either down or right to get to the bottom right corner of the square, and along the way you collect each value at each square. What is the optimal path to walk to maximize your score?

5   9   2

2   8   5

9   2   3

In this simple example, the optimal path is shown below:

5 - 9   2
     |
2   8 - 5
        |
9   2   3

The maximum score you can achieve is 5 + 9 + 8 + 5 + 3 = 30. Like before, this problem is solvable with brute force - that is, check all possible paths from the top left corner to the bottom right corner and take the maximum. However, obviously this solution is extremely slow, running in O(2^N) time where N is the side length of the square.

We can use the dynamic programming idea of using smaller solutions again in this problem. Let's consider a labeled version of our square grid:

1   2   3

4   5   6

7   8   9

In order to reach square 9, we must come from either square 8 or square 6. Knowing this, the best possible result at square 9 is the maximum of the best possible result at square 8 or the best possible result at square 6, plus the value at square 9. Similarly, the solution at square 6 is the maximum of the solutions at squares 5 and 3 plus the value at square 6. With this process, we use our previous solutions to calculate the larger solutions.

Our algorithm will look something like this: iterate through the grid left to right and top to bottom. Replace each square's value with the maximum of the squares which we can come from, plus the value of the current square. In this way, we can use dynamic programming to calculate the maximum possible value of a path. This algorithm runs in O(N^2) time, a huge speed improvement. Here is an implementation in JavaScript:

// data

const grid = [[5, 9, 2],
              [2, 8, 5],
              [9, 2, 3]]

// iterate through grid

for (let a = 0; a < grid.length; a ++) {
    for (let b = 0; b < grid[a].length; b ++) {
        // take the maximum of valid squares

        let max_value = 0
        if (a > 0) {
            max_value = Math.max(max_value, grid[a - 1][b])
        }
        if (b > 0) {
            max_value = Math.max(max_value, grid[a][b - 1])
        }

        // set value at current square

        grid[a][b] += max_value
    }
}

// our solution is value at last square
console.log("optimal sum:", grid[grid.length - 1][grid[0].length - 1])

Run the solution here: https://repl.it/@MrEconomical/dp-path-walk

However, there is one important thing to note: the order by which we iterate through the grid matters! If we try to take the maximum of two squares before their solutions have been calculated, then our result will not make any sense. When doing dynamic programming, we must carefully consider how our algorithm progresses and always make sure the previous solutions are calculated before we use them.

Key Concepts

Think about how to simplify the problem - Often, coming up with the dynamic programming algorithm is harder than implementing it. You should always think about how to break up the current problem into a series of smaller problems, and how to break up those smaller problems even further. Not all problems are solvable with dynamic programming, but often if you can figure out how to break down the problems, dynamic programming is possible.

Store previous solutions - In dynamic programming, we almost always store our previous solutions using a table. This way, we can access the data we need when we need to use it to calculate our next solution. We use these smaller solutions to build the final answer.

Order matters - The order of your iterations is extremely important! If you iterate in the wrong order, you will try to access solutions that you have not calculated yet, leading to incorrect results. Make sure that you really are calculating everything in the correct order.

I hope this tutorial was helpful and not too hard to understand! The next tutorial in the series will be about some more advanced dynamic programming problems.

Commentshotnewtop
AtticusKuhn (236)

Dynamic Programming is like magic

DynamicSquid (2254)

@AtticusKuhn Dynamic Programming Squid is like magic

DynamicSquid (2254)

Guys, this is an April Fool's prank. None of it's true. Nice try @MrEconomical, but you can't fool everyone

No but seriously, this is another great tutorial, well done!

StudentFires (327)

@DynamicSquid He had me fooled, I should’ve seen it coming. Your comment actually made me laugh, good job!

[deleted]

Actually, it’s true. @DynamicSquid

Roar123 (425)

Great job! I really like your approach for walking through code and problems

LeonardoMacedo1 (0)

Friend escaping the subject a little, is it possible to decrypt a file.lua that the script is made with loadstring?