We just published a comprehensive Dynamic Programming course on the freeCodeCamp.org YouTube channel that uses a visual-first approach to learn these complex algorithms.

Created by Sheldon, an ex-Google engineer with over 10 years of experience, this course focuses on helping you develop a visual intuition for optimization. Instead of asking you to memorize hundreds of individual problems, Sheldon teaches you to recognize the underlying patterns that connect them.

The course breaks down dynamic programming into six fundamental patterns, explaining the logic and code (using Python) for each:

1. Constant Transition: Learn the basics with problems like the Climbing Stairs and House Robber, where the state depends on a fixed number of previous states.

2. Grid Pattern: Explore 2D dynamic programming with problems like Unique Paths, learning how to build tables to solve navigation challenges.

3. Two Sequences: Discover how to compare strings and sequences using 2D tables, covering classics like Longest Common Subsequence and Edit Distance.

4. Interval DP: Tackle problems involving finding optimal substructures within intervals, such as the Longest Palindromic Subsequence.

5. Non-Constant Transition: Understand complex transitions where a state depends on a variable number of previous states, illustrated by the Longest Increasing Subsequence problem.

6. Knapsack-Like Problems: Master problems involving building specific sums or filling capacities, such as Partition Equal Subset Sum and Coin Change.

Watch the full course on the freeCodeCamp.org YouTube channel (2-hour watch).

We just published a new course on the freeCodeCamp.org YouTube channel that offers a deep dive into the world of the 0/1 Knapsack Problem. You will learn how it works and discover how to build an efficient solution from scratch using C#. Gavin Lon developed this course.

The Knapsack Problem is often used as a pedagogical tool to teach two important paradigms in algorithm design: Dynamic Programming and Greedy Algorithms.

And if you're an aspiring programmer participating in job interviews, it could be a game-changer. Algorithmic interviews often touch upon optimization problems, and the strategies you'll learn here can be applied far beyond the knapsack.

Course Breakdown

1. Introduction: Set the stage with a brief overview of what to expect throughout the course. Get a taste of the problem's historical significance and its place in the grand tapestry of computer science.
2. Overview of the 0/1 Knapsack Problem: Dive into the heart of the matter. What exactly is this problem? Why is it termed "0/1"? Gavin demystifies the challenge, outlining the problem statement, its constraints, and real-world applications.
3. Code the Algorithm Using C#: Transition from theory to practice. Follow Gavin as he demonstrates how to translate the problem into code, using the robust and versatile C# language.
4. Dynamic Programming & Memoization Strategy: Here's where the magic happens. Learn about the power of Dynamic Programming, a technique to simplify complex problems by breaking them down into smaller, more manageable subproblems. Get introduced to the concept of memoization, a strategy to store and reuse previously computed results, ensuring the algorithm runs in optimal time.
5. Outputting the Items for the Knapsack in C#: It's not just about finding the maximum value—it's also about identifying which items to pack. In this section, Gavin will guide you through the process of extracting the actual items to include in the knapsack, making your solution complete.

The course is available right now, for free, on the freeCodeCamp.org YouTube channel (1-hour watch).

We just posted a course on the freeCodeCamp.org YouTube channel that will teach you Dynamic Programming techniques with Java.

Alvin Zablan created this course. It provides a deep dive into dynamic programming and teaches a lot of key algorithms.

What is Dynamic Programming?

Dynamic programming is a method for solving complex problems by breaking them down into simpler sub-problems. It is a way to solve problems by using solutions to smaller instances of the same problem.

The key idea behind dynamic programming is quite simple. In general, to solve a problem, you solve some sub-problems. Dynamic programming is used when the sub-problems are not independent, i.e., when sub-problems share sub-sub-problems. In this context, divide and conquer algorithms do more work than necessary, repeatedly solving the common sub-sub-problems. Dynamic programming algorithms remember past results and use them to find new results.

When is Dynamic Programming Used?

Dynamic programming is often used in optimization problems where we have to find the best solution among a set of feasible solutions. It's particularly useful when a problem has overlapping sub-problems. Instead of computing solutions to these sub-problems repeatedly, dynamic programming suggests solving each of these sub-problems just once, saving their solutions, and returning the saved solution when the same sub-problem is encountered again.

Dynamic Programming in Coding Interviews

Dynamic programming is a favorite topic in coding interviews. Interviewers love to test the understanding, analytical skills, and problem-solving abilities of candidates using dynamic programming problems. It's not just about knowing the technique but also about understanding when and how to use it. Mastering dynamic programming can give you a significant edge in coding interviews.

Course Breakdown

Here are the sections covered in the course:

1. fib: Dive into the Fibonacci sequence, a classic example to kickstart your dynamic programming journey.
2. tribonacci: Explore the tribonacci sequence, a variation of the Fibonacci sequence.
3. sum possible: Learn to determine if a sum is possible with given numbers.
4. min change: Find out the minimum change required from a set of denominations.
5. count paths: Count the number of paths in a grid.
6. max path sum: Calculate the maximum path sum in a grid.
7. non adjacent sum: Find the maximum sum without adding adjacent numbers.
8. summing squares: Understand the concept of summing squares in dynamic programming.
9. counting change: Learn different ways to count change using given denominations.

Whether you're a beginner looking to understand the basics of dynamic programming or an advanced coder aiming to brush up your skills, this course has something for everyone.

You can watch the full course on the freeCodeCamp.org YouTube channel (3-hour watch).

Understanding Dynamic Programming can help you solve complex programming problems faster.

These methods can help you ace programming interview questions about data structures and algorithms. And they can improve your day-to-day coding as well.

We released a 5-hour course on Dynamic Programming on the freeCodeCamp.org YouTube channel.

Alvin Zablan developed this course. Alvin is an experienced programming instructor at Coderbyte, a popular website for technical interview prep and coding challenges.

In this course you will learn to use Dynamic Programming strategies to solve programming challenges such as:

• Calculating the 40th number of the Fibonacci sequence.
• Counting the number of different ways to move through a 6x9 grid.
• Given a set of coins, how can you make 27 cents in the least number of coins.

This course uses images and animations to help you visualize problems and important concepts. After understanding problems conceptually, you will learn how to solve them in JavaScript using Dynamic Programming.

Even though this course uses JavaScript, you will learn concepts and knowledge that you can apply to other programming languages, including Python.

Dynamic Programming can really speed up your work. But common sense can speed things up even further. (Traveling Salesman problem webcomic by XKCD)

Dynamic Programming Methods This Course Covers

Part one of this course focuses on Memoization methods. This is where you use recursion and store the intermediate results of your algorithm. You can then access those results on later trips through your your loops.

Here are the Memoization strategies this course covers:

• fib memoization
• gridTraveler memoization
• memoization recipe
• canSum memoization
• howSum memoization
• bestSum memoization
• canConstruct memoization
• countConstruct memoization
• allConstruct memoization

And part two focuses on Tabulation strategies. These involve building up a table of data iteratively.

Here are the Tabulation strategies this course covers:

• fib tabulation
• gridTraveler tabulation
• tabulation recipe
• canSum tabulation
• howSum tabulation
• bestSum tabulation
• canConstruct tabulation
• countConstruct tabulation
• allConstruct tabulation

You can watch the full course on the freeCodeCamp.org YouTube channel (5-hour watch).

Dynamic Programming is an approach where the main problem is divided into smaller sub-problems, but these sub-problems are not solved independently.

For a problem to be solved using dynamic programming, the sub-problems must be overlapping. This means that two or more sub-problems will evaluate to give the same result.

So, we use the memoization technique to recall the result of the already solved sub-problems for future use. We then use cache storage to store this result, which is used when a similar sub-problem is encountered in the future.

Now let's look at this topic in more depth.

What is memoization?

Memoization is the technique of memorizing the results of certain specific states, which can then be accessed to solve similar sub-problems. In other words, it is a specific form of caching.

This ensures that the results already computed are stored generally as a hashmap. This decreases the run time significantly, and also leads to less complicated code.

But we know that any benefit comes at the cost of something. So, when we use dynamic programming, the time complexity decreases while space complexity increases.

Different approaches in DP

In dynamic programming, we can either use a top-down approach or a bottom-up approach.

The top-down approach involves solving the problem in a straightforward manner and checking if we have already calculated the solution to the sub-problem.

This approach includes recursive calls (repeated calls of the same function). It builds up a call stack, which leads to memory costs. It is also vulnerable to stack overflow errors.

The bottom-up approach includes first looking at the smaller sub-problems, and then solving the larger sub-problems using the solution to the smaller problems.

This approach avoids memory costs that result from recursion.

But both the top-down approach and bottom-up approach in dynamic programming have the same time and space complexity. So in the end, using either of these approaches does not make much difference.

Just a quick note: dynamic programming is not an algorithm. But I have seen some people confuse it as an algorithm (including myself at the beginning).

It is used only when we have an overlapping sub-problem or when extensive recursion calls are required. It is a way to improve the performance of existing slow algorithms.

This means, also, that the time and space complexity of dynamic programming varies according to the problem.

Dynamic Programming Example

Now let us solve a problem to get a better understanding of how dynamic programming actually works.

Consider the problem of finding the longest common sub-sequence from the given two sequences.

⇒ ‘gtcab’ and ‘gxtxab’

We can solve this problem using a naive approach, by generating all the sub-sequences for both and then find the longest common sub-sequence from them.

But the time complexity of this solution grows exponentially as the length of the input continues increasing.

So, how do we know that this problem can be solved using dynamic programming?‌‌‌‌

For the two strings we have taken, we use the below process to calculate the longest common sub-sequence (LCS).

As we can see, here we divide the main problem into smaller sub-problems. Let us check if any sub-problem is being repeated here.

Dividing the main problem into sub-problems

‌‌We can see here that two sub-problems are overlapping when we divide the problem at two levels.

If we further go on dividing the tree, we can see many more sub-problems that overlap. So we conclude that this can be solved using dynamic programming.

Next, let us look at the general approach through which we can find the longest common sub-sequence (LCS) using dynamic programming.

How to fill the matrix?

We will use the matrix method to understand the logic of solving the longest common sub-sequence using dynamic programming.

Here we will only discuss how to solve this problem – that is, the algorithm part. And for that we use the matrix method.

Look at the below matrix. We have filled the first row with the first sequence and the first column with the second sequence.

Then we populated the second row and the second column with zeros for the algorithm to start. We denote the rows with ‘i’ and columns with ‘j’.

Matrix entry

Now we move on to fill the cells of the matrix. Compare the two sequences until the particular cell where we are about to make the entry.

The length/count of common sub-sequences remains the same until the last character of both the sequences undergoing comparison becomes the same.

If the sequences we are comparing do not have their last character equal, then the entry will be the maximum of the entry in the column left of it and the entry of the row above it.

When the last characters of both sequences are equal, the entry is filled by incrementing the upper left diagonal entry of that particular cell by 1.

The logic we use here to fill the matrix is given below:‌

if(input[i]==input[j])              //Check if last characters are equal
T[i][j]=T[i-1][j-1]+1               //Entry is incremental of upper left element
else                                //If the last character are not equal
T[i][j]=max(T[i-1][j], T[i][j-1])   //Entry is max of element to its left and top

The bottom right entry of the whole matrix gives us the length of the longest common sub-sequence.

Finding the longest common sub-sequence

In order to get the longest common sub-sequence, we have to traverse from the bottom right corner of the matrix. Then we check from where the particular entry is coming.

That is, we can check whether it is the maximum of its left and top entry or else is it the incremental entry of the upper left diagonal element?

We repeat this process until we reach the top left corner of the matrix. The sub-sequence we get by combining the path we traverse (only consider those characters where the arrow moves diagonally) will be in the reverse order.

We have to reverse this obtained sequence to get the correct longest common sub-sequence. So in this particular example, the longest common sub-sequence is ‘gtab’.

I have made a detailed video on how we fill the matrix so that you can get a better understanding. You can find it here: Video Explanation.

What did we learn?

In this article, we learned what dynamic programming is and how to identify if a problem can be solved using dynamic programming.

Then we went on to study the complexity of a dynamic programming problem.

Next we learned how we can solve the longest common sub-sequence problem using dynamic programming.

I hope you enjoyed it and learned something useful from this article.

If you found this post helpful, please share it. If you have any feedback, feel free to contact me on Twitter.

Previously, I wrote about solving the Knapsack Problem (KP) with dynamic programming. You can read about it here.

Today I want to discuss a variation of KP: the partition equal subset sum problem. I first saw this problem on Leetcode — this was what prompted me to learn about, and write about, KP.

This is the problem statement (reproduced partially without examples):

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

For the full problem statement, with constraints and examples, check out the Leetcode problem.

Dynamic programming

Like with KP, we’ll be solving this using dynamic programming. Since this is a variation of KP, the logic and methodology is largely similar.

Solution

We will house our solution in a method that returns a boolean — true if the array can be partitioned into equal subsets, and false otherwise.

Step 1: Guarding against odd array sum

Trivially, if all the numbers in the array add up to an odd sum, we can return false. We only proceed if the array adds up to an even sum.

Step 2: Creating the table

Next, we create the table.

Table rows represent the set of array elements to be considered, while table columns indicate the sum we want to arrive at. Table values are simply boolean values, indicating whether a sum (column) can be arrived at with a set of array elements (row).

Concretely, row i represents a set of array elements from indices 0 to (i-1). The reason for this offset of 1 is because row 0 represents an empty set of elements. Therefore, row 1 represents the first array element (index 0), row 2 represents the first two array elements (indices 0–1), and so on. In total, we create n + 1 rows, inclusive of 0.

We only want to know if we can sum up exactly to half the total sum of the array. So we only need to create totalSum / 2 + 1 columns, inclusive of 0.

Step 3: Pre-filling the table

We can immediately begin filling the entries for the base cases in our table — row 0 and column 0.

In the first row, every entry — except the first — must be false. Recall that the first row represents an empty set . Naturally, we are unable to arrive at any target sum — column number — except 0.

In the first column, every entry must be true. We can always,trivially, arrive at a target sum of 0, regardless of the set of elements we have to work with.

Step 4: Building the table (the crux of the problem)

Some entry in the table at row i and column j is true (attainable) if one of the following three conditions are satisfied:

1. the entry at row i-1 and column j is true. Recall what the row number represents. Therefore, if we are able to attain a particular sum with a subset of the elements that we have presently, we can also attain that sum with our current set of elements — by simply not using the extra elements. This is trivial. Let’s call this prevRowIsTrue.
2. The current element is exactly the sum we want to attain. This is also trivially true. Let’s call this isExactMatch.
3. If the above two conditions are not satisfied, we have one remaining way of attaining our target sum. Here, we use the current element — the additional element in the set of elements in our current row compared to the set of elements in the previous row — and check that we are able to attain the remainder of the target sum. Let’s call this canArriveAtSum.

Let’s unpack condition 3. We can only use the current element if it is less than our target sum. If they’re equal, condition 2 would be satisfied. If it’s larger, we can’t use it. Therefore, the first step is to ensure that current element < target sum.

After using our current element, we are left with the remainder of our target sum. We then check if that is attainable by checking the corresponding entry in the row above.

As with regular KP, we want to progressively build our table from the bottom-up. We start with the base cases, until we arrive at our final solution.

Step 5: Returning the answer

We simply return return mat[nums.length][totalSum / 2].

Working code

Thanks for reading!

Suppose you are doing some calculation using an appropriate series of input. There is some computation done at every instance to derive some result. You don’t know that you had encountered the same output when you had supplied the same input. So it’s like you are doing re-computation of a result that was previously achieved by specific input for its respective output.

But what’s the problem here? Thing is that your precious time is wasted. You can easily solve the problem here by keeping records that map previously computed results. Such as using the appropriate data structure. For example, you could store input as key and output as a value (part of mapping).

Those who cannot remember the past are condemned to repeat it. ~Dynamic Programming

Now by analyzing the problem, store its input if it’s new (or not in the data structure) with its respective output. Else check that input key and get the resultant output from its value. That way when you do some computation and check if that input existed in that data structure, you can directly get the result. Thus we can relate this approach to dynamic programming techniques.

Diving into dynamic programming

In a nutshell, we can say that dynamic programming is used primarily for optimizing problems, where we wish to find the “best” way of doing something.

A certain scenario is like there are re-occurring subproblems which in turn have their own smaller subproblems. Instead of trying to solve those re-appearing subproblems, again and again, dynamic programming suggests solving each of the smaller subproblems only once. Then you record the results in a table from which a solution to the original problem can be obtained.

For instance, the Fibonacci numbers 0,1,1,2,3,5,8,13,… have a simple description where each term is related to the two terms before it. If F(n) is the nth term of this series then we have F(n) = F(n-1) + F(n-2). This is called a recursive formula or a recurrence relation. It needs earlier terms to have been computed in order to compute a later term.

The majority of Dynamic Programming problems can be categorized into two types:

1. Optimization problems.
2. Combinatorial problems.

The optimization problems expect you to select a feasible solution so that the value of the required function is minimized or maximized. Combinatorial problems expect you to figure out the number of ways to do something or the probability of some event happening.

An approach to solve: top-down vs bottom-up

There are the following two main different ways to solve the problem:

Top-down: You start from the top, solving the problem by breaking it down. If you see that the problem has been solved already, then just return the saved answer. This is referred to as Memoization.

Bottom-up: You directly start solving the smaller subproblems making your way to the top to derive the final solution of that one big problem. In this process, it is guaranteed that the subproblems are solved before solving the problem. This can be called Tabulation (table-filling algorithm).

In reference to iteration vs recursion, bottom-up uses iteration and the top-down uses recursion.

The visualization displayed in the image is not correct acc. to theoretical knowledge, but I have displayed in an understandable manner

Here there is a comparison between a naive approach vs a DP approach. You can see the difference by the time complexity of both.

Memoization: Don’t forget

Jeff Erickson describes in his notes, for Fibonacci numbers:

The obvious reason for the recursive algorithm’s lack of speed is that it computes the same Fibonacci numbers over and over and over.

_From Jeff Erickson’s notes CC: [http://jeffe.cs.illinois.edu/](http://jeffe.cs.illinois.edu/" rel="noopener" target="blank" title=")

We can speed up our recursive algorithm considerably just by writing down the results of our recursive calls. Then we can look them up again if we need them later.

Memoization refers to the technique of caching and reusing previously computed results.

If you use memoization to solve the problem, you do it by maintaining a map of already solved subproblems (as we earlier talked about the mapping of key and value). You do it “top-down” in the sense that you solve the “top” problem first (which typically recurses down to solve the sub-problems).

Pseudocode for memoization:

So using recursion, we perform this with extra overhead memory (i.e. here lookup) to store results. If there is a value stored in the lookup, we return it directly or we add it to lookup for that specific index.

Remember that there is a tradeoff of extra overhead with respect to the tabulation method.

However, if you want more visualizations for memoization, then I suggest looking into this video.

In a top-down manner.

Tabulation: Filling up in tabular form

But once we see how the array (memoized solution) is filled, we can replace the recursion with a simple loop that intentionally fills the array in order, instead of relying on the complicated recursion to do it for us ‘accidentally’.

_From Jeff Erickson’s notes CC: [http://jeffe.cs.illinois.edu/](http://jeffe.cs.illinois.edu/" rel="noopener" target="blank" title=")

Tabulation does it in “bottom-up” fashion. It’s more straight forward, it does compute all values. It requires less overhead as it does not have to maintain mapping and stores data in tabular form for each value. It may also compute unnecessary values. This can be used if all you want is to compute all values for your problem.

Pseudocode for tabulation:

Pseudocode with Fibonacci tree

As you can see pseudocode (right side) in an image, it does iteration (i.e. loops over till the end of an array). It simply starts with fib(0),fib(1),fib(2),… So with the tabulation approach, we can eliminate the need for recursion and simply return the result with looping over elements.

Looking back in history

Richard bellman was the man behind this concept. He came up with this when he was working for RAND Corporation in the mid-1950s. The reason he chose this name “dynamic programming” was to hide the mathematics work he did for this research. He was afraid his bosses would oppose or dislike any kind of mathematical research.

Okay, so the word ‘programming’ is just a reference to clarify that this was an old-fashioned way of planning or scheduling, typically by filling in a table (in a dynamic manner rather than in a linear way) over the time rather than all at once.

Wrapping up

That’s it. This is part 2 of the algorithm series I started last year. In my previous post, we discussed about what are searching and sorting algorithms. Apologies that I couldn’t deliver this in a shorter time. But I am willing to make things faster in the coming months.

Hope you liked it and I’ll be soon looking to add a third one in the series soon. Happy coding!

Resources:

Introduction to Dynamic Programming 1 Tutorials & Notes | Algorithms | HackerEarth
_The image above says a lot about Dynamic Programming. So, is repeating the things for which you already have the…_www.hackerearth.comCommunity — Competitive Programming — Competitive Programming Tutorials — Dynamic Programming: From…
_Community — Competitive Programming — Competitive Programming Tutorials — Dynamic Programming: From Novice to Advanced_www.topcoder.com

https://www.geeksforgeeks.org/overlapping-subproblems-property-in-dynamic-programming-dp-1/

Special props to Jeff Erickson and his notes for algorithm — http://jeffe.cs.illinois.edu/

If you’re a competitive programmer like I am, one of the best feelings in the world is seeing your program getting accepted on first try on one of the most famous programming platforms, CodeChef.

I was an avid competitive programmer during undergrad, and then lost touch with it when working as a developer @Hike. However, I recently started out into this adventurous world of programming again, all thanks to my friend Divya Godayal.

The CodeChef May 2018 Long Challenge ended about an hour ago, and I decided to write this article as a post describing one of the questions in the competition.

Without wasting any more time, let’s get to it.

Unravelling the Problem Statement

Let’s look at some examples to better understand what the problem statement is asking for.

Consider the following number sequence.

4 3 1 2

Now the question asks us to perform a certain operation (possibly 0 times, leaving the sequence unchanged). We can negate a certain subsequence of numbers and get a new sequence.

-4 3 1 24 -3 1 -24 3 -1 24 3 1 -2-4 -3 1 2 etc.

The question says that the resulting sequence should satisfy the following constraint:

The sum of elements of any substring with length greater than 1 is strictly positive.

Clearly, the following sequences are not valid:

-4 3 1 24 -3 1 -2 4 3 1 -2 -4 -3 1 2 -4 -3 -1 -24 3 -1 -2

We only have 2 valid subsequences that can be obtained by performing the operation mentioned above. Note: we haven’t written down all the possible subsequences. That would be 2^n, that is 16 in this case, because for every number we have two options. Either to negate it, or not.

So the two valid sequences are:

4 3 1 2

and

4 3 -1 2

The original sequence would always be one of the valid sequences as all the numbers in it are positive.

Now the question asks us to find the sequence with the minimum sum. So for the example we have considered, the sequence required would be 4 3 -1 2 .

Would Greedy Work?

A greedy approach in this question would be that if it is possible to negate a number while satisfying the given constraints, then we should negate that number. This approach however, would not always give the right results. Consider the following example.

4 1 3 2

Here, it is possible to have these three valid sets of numbers:

4 1 3 2           4 -1 3 2           4 1 3 -2

Clearly, both the numbers 2 and 1 can be negated. But not both of them at the same time. If we negate a number greedily — that is, if a number can be negated, then we negate it — then it is possible that we might end up negating the number 1. Then you won’t be able to negate the number 2. This would give us a suboptimal solution.

So this Greedy approach would not work here. We have to “try out a specific choice of whether to negate or not for a number and see what choice gives us the optimal solution”.

This smells like Dynamic Programming.

Good ol’ Dynamic Programming

One of the most interesting algorithmic techniques out there, and possibly one of the most dreaded, is dynamic programming. This is the technique we are going to use to solve this particular problem.

Two of the most important steps in any dynamic programming problem are:

1. Identifying the recurrent relation.
2. Figuring out what to memoize. (not memoRize :P)

The DP-based approach here is divided into two basic parts.

• One is the main recursion that we use to find out the minimum sum of the final set. Note, the dynamic programming is not directly used to obtain the final set, just the sum of the final set of numbers. So our dynamic programming approach would correctly find out the sum for the example given above as 8. 4 + 3 + (-1) + 2 = 8 .
• What we actually need is the final modified set of numbers where some (possibly none) of the numbers are negated. We use the concept of a parent pointer and backtracking to find out the actual set of numbers.

Let’s move onto our recursion relation for our dynamic programming approach.

Before describing the recursive relation an important observation to make here is that if a number has been negated, then any adjacent number to it can not be negative. That is, two adjacent numbers cannot be negative as that would give a substring of length 2 whose sum is negative, and that is not allowed according to the question.

For the recurrence relation, we need two variables. One is the index number of where we are in the array, and one is a boolean value that tells us if the previous number (one left to the previous number) is negated or not. So if the current index is i, then the boolean value would tell us if the number at i — 2 was negated or not. You will know the importance of this boolean variable in the next paragraph.

We need to know in O(1) if a number can be negated or not. Since we are following a recursion with memoization-based solution, whenever we are at an index i in the recursion, we are sure that the numbers to the right (i+ 1 onwards) have not been processed up to this point. This means that all of them are still positive.

The choice of whether the number at index i can be negated is dependent upon the right hand side (if there is one) and the left hand side (if there is one). The right hand side is easy. All we need to check is if

number[i] < number[i + 1]

because if this is not true, then adding these two would give a negative value for the substring [i, i + 1] thus making it an invalid operation.

Now comes the tricky part. We need to see if negating the number at i will cause a substring of negative sum to the left or not. When we reach the index i in our recursion, we have already processed the numbers before it, and some might have been negated as well.

So say we have this set of numbers 4 1 2 1 and we had negated the first 1 and we are now processing the last number ( 1 ).

4 -1 2 [1]

The last number in square brackets is the one we are processing right now. As far as the right hand side is concerned, since there is none, we can negate it. We need to check if negating this 1 at index 3 (0 based indexing) would cause any substring to the left of ≤ 0 sum. As you can see, it will produce such a substring.

-1 2 -1

This substring would have a 0 sum, and that is invalid according to the question. After negating a subsequence of numbers, the substrings in the final set should have a sum which is strictly positive. All the substrings of length > 1.

We cannot apply the following approach here directly:

if number[i] < number[i - 1], then it is good to go on negation.

because, although 1 <; 2 , if we negate that last 1 as well we will have an invalid set of numbers as seen above. So this simple approach or check won’t work here.

Here comes the boolean variable which tells us if, given an index i, the number at i — 2 was negated or not. Consider the two scenarios.

• Yes, the number at index i — 2 was negated like in the example just showcased. In that case, negation of the number at i — 2 would have a capacity reduction for number at i — 1. In the example 4 1 2 1 , negating the 1 at index 1(0 based indexing) would reduce the capacity of the number 2 (at index 2) by 1. We refer to remaining values of numbers as capacities here. We need to consider this reduced capacity when performing the check to see if a number can be negated or not.

number[i] < reducedCapacityOfNumberAt(i - 1)

• In case the number at index i — 2 wasn’t negated, the number at i — 1 is at it’s full capacity. The simple check

number[i] < number[i - 1]

would be enough to see if we can negate the number at index i .

Let’s look at the code for the recursion containing all the ideas discussed above.

That’s all nice and dandy. But, this is just recursion, and the heading says dynamic programming. That means there would be overlapping subproblems. Let us look at the recursion tree to see if there are any.

As you can see, there are overlapping subproblems in the recursion tree. That is why we can use memoization.

The memoization is as simple as:

""" This comes at the top. We check if the state represented by the tuple of the index and the boolean variable is already cached """

if(memo[i][is_prev_negated] != INF) {    return memo[i][is_prev_negated];}

...... CODE

# Cache the minimum sum from this index onwards.memo[i][is_prev_negated] = min(pos, neg);

# The parent pointer is used for finding out the final set of #sparent[i][is_prev_negated] = min(pos, neg) == pos ? 1 : -1;

As pointed out earlier, this recursive approach would return the minimum sum of the set of numbers possible after making the valid set of modifications to them.

The question, however, asks us to actually print the final set of numbers that gives the minimum sum after making such modifications. For that, we need to use a parent pointer that would tell us at every index and boolean variable is_prev_negated ’s value as to what optimal action was taken.

parent[i][is_prev_negated] = min(pos, neg) == pos ? 1 : -1;

So we simply store 1 or -1 depending upon if negating the number at index i (if possible!) gave us the minimum sum or if choosing to ignore it gave the minimum sum.

Backtracking

Now comes the part where we backtrack to find the solution to our original problem. Note that the decision for the very first number is what propagates the recursion further. If the first number was negated, the second number would be positive and the third number’s decision can be found using parent[2][true]. Similarly, if the first number wasn’t negated, then we move onto the second number and it’s decision can be found using parent[1][false] and so on. Let’s look at the code.

A Better Approach

If you take a look at the space complexity of the solution suggested, you will see that it’s a 2 dimensional dynamic programming solution because the state of the recursion is represented by two variables i.e. the index i representing what number of the array we are considering and then the boolean variable is_prev_negated . So the space complexity and the time complexity would be O(n*2) which is essentially O(n).

However, there is a slightly better approach as well to solving this problem as suggested by Divya Godayal. This problem can even be solved by 1 dimensional dynamic programming based solution.

Essentially, the boolean variable is_prev_negated is helping us to decide if we can negate a given number at index i or not as far as the left hand side of the array is concerned i.e. all the numbers from 0 .. i-1 because the right hand side is anyways safe as all the numbers on that side are positive (as the recursion hasn’t reached them yet). So for the right hand side we simply checked the number at i+1 but for the left hand side of index i we had to make use of the boolean variable is_prev_negated .

It turns out, that we can simply skip this boolean variable altogether and simply look ahead to decide if a number can be negated or not. Which simply means if you are at an index i, you check if that element along with the element at i+2 have the capacity to swallow the element at i+1 i.e.

numbers[i] + numbers[i+2] >= numbers[i+1  (SWALLOW)

If there is a such a possibility, then we directly jump to i+3if we negate element at i because element at i+1 and i+2 both can’t be negative in such a scenario.

In case the swallow condition is not satisfied and we end up negating the number at index i , then we would jump to index i+2 because in any case, two consecutive numbers cannot be negated. So if the number at i was negated, then the number at i+1 has to be positive. The swallow check is to see if the number at i+2 would definitely have to be positive or if we can exercise the choice of whether to negate or not there.

Have a look at the code for a better understanding.

Hence, just a single variable i.e. the index is used to define the state of the recursion. So the time and space complexity, both got reduced to half of what they were in the previous solution.

I hope you were able to grasp the working of the algorithm described above and how the dynamic programming technique fits into this problem. I think it’s an interesting problem, because you not only have to use dynamic programming but also the concept of parent pointer to retrace the steps through the optimal solution and get the answer required in the question.

How to construct & code dynamic programming algorithms

Maybe you’ve heard about it in preparing for coding interviews. Maybe you’ve struggled through it in an algorithms course. Maybe you’re trying to learn how to code on your own, and were told somewhere along the way that it’s important to understand dynamic programming. Using dynamic programming (DP) to write algorithms is as essential as it is feared.

And who can blame those who shrink away from it? Dynamic programming seems intimidating because it is ill-taught. Many tutorials focus on the outcome — explaining the algorithm, instead of the process — finding the algorithm . This encourages memorization, not understanding.

During my algorithms class this year, I pieced together my own process for solving problems that require dynamic programming. Parts of it come from my algorithms professor (to whom much credit is due!), and parts from my own dissection of dynamic programming algorithms.

But before I share my process, let’s start with the basics. What is dynamic programming, anyway?

Dynamic Programming Defined

Dynamic programming amounts to breaking down an optimization problem into simpler sub-problems, and storing the solution to each sub-problem so that each sub-problem is only solved once.

To be honest, this definition may not make total sense until you see an example of a sub-problem. That’s okay, it’s coming up in the next section.

What I hope to convey is that DP is a useful technique for optimization problems, those problems that seek the maximum or minimum solution given certain constraints, because it looks through all possible sub-problems and never recomputes the solution to any sub-problem. This guarantees correctness and efficiency, which we cannot say of most techniques used to solve or approximate algorithms. This alone makes DP special.

In the next two sections, I’ll explain what a sub-problem is, and then motivate why storing solutions — a technique known as memoization — matters in dynamic programming.

Sub-problems on Sub-problems on Sub-problems

Sub-problems are smaller versions of the original problem. In fact, sub-problems often look like a reworded version of the original problem. If formulated correctly, sub-problems build on each other in order to obtain the solution to the original problem.

To give you a better idea of how this works, let’s find the sub-problem in an example dynamic programming problem.

Pretend you’re back in the 1950s working on an IBM-650 computer. You know what this means — punchcards! Your job is to man, or woman, the IBM-650 for a day. You’re given a natural number n punchcards to run. Each punchcard i must be run at some predetermined start time _si and stop running at some predetermined finish time _fi. Only one punchcard can run on the IBM-650 at once. Each punchcard also has an associated value _vi based on how important it is to your company.

Problem: As the person in charge of the IBM-650, you must determine the optimal schedule of punchcards that maximizes the total value of all punchcards run.

Because I’ll go through this example in great detail throughout this article, I’ll only tease you with its sub-problem for now:

Sub-problem: The maximum value schedule for punchcards i through n such that the punchcards are sorted by start time.

Notice how the sub-problem breaks down the original problem into components that build up the solution. With the sub-problem, you can find the maximum value schedule for punchcards n-1 through n, and then for punchcards n-2 through n, and so on. By finding the solutions for every single sub-problem, you can then tackle the original problem itself: the maximum value schedule for punchcards 1 through n. Since the sub-problem looks like the original problem, sub-problems can be used to solve the original problem.

In dynamic programming, after you solve each sub-problem, you must memoize, or store it. Let’s find out why in the following section.

Motivating Memoization with Fibonacci Numbers

When told to implement an algorithm that calculates the Fibonacci value for any given number, what would you do? Most people I know would opt for a recursive algorithm that looks something like this in Python:

def fibonacciVal(n):  if n == 0:    return 0  elif n == 1:    return 1  else:    return fibonacciVal(n-1) + fibonacciVal(n-2)

This algorithm accomplishes its purpose, but at a huge cost. For example, let’s look at what this algorithm must calculate in order to solve for n = 5 (abbreviated as F(5)):

F(5)                      /      \                                     /        \                  /          \               F(4)          F(3)            /       \        /   \          F(3)     F(2)     F(2)  F(1)         /   \     /  \     /   \       F(2) F(1) F(1) F(0) F(1) F(0)       /  \     F(1) F(0)

The tree above represents each computation that must be made in order to find the Fibonacci value for n = 5. Notice how the sub-problem for n = 2 is solved thrice. For a relatively small example (n = 5), that’s a lot of repeated , and wasted, computation!

What if, instead of calculating the Fibonacci value for n = 2 three times, we created an algorithm that calculates it once, stores its value, and accesses the stored Fibonacci value for every subsequent occurrence of n = 2? That’s exactly what memoization does.

With this in mind, I’ve written a dynamic programming solution to the Fibonacci value problem:

def fibonacciVal(n):  memo = [0] * (n+1)  memo[0], memo[1] = 0, 1  for i in range(2, n+1):    memo[i] = memo[i-1] + memo[i-2]  return memo[n]

Notice how the solution of the return value comes from the memoization array memo[ ], which is iteratively filled in by the for loop. By “iteratively,” I mean that memo[2] is calculated and stored before memo[3], memo[4], …, and memo[n]. Because memo[ ] is filled in this order, the solution for each sub-problem (n = 3) can be solved by the solutions to its preceding sub-problems (n = 2 and n = 1) because these values were already stored in memo[ ] at an earlier time.

Memoization means no re-computation, which makes for a more efficient algorithm. Thus, memoization ensures that dynamic programming is efficient, but it is choosing the right sub-problem that guarantees that a dynamic program goes through all possibilities in order to find the best one.

Now that we’ve addressed memoization and sub-problems, it’s time to learn the dynamic programming process. Buckle in.

My Dynamic Programming Process

Step 1: Identify the sub-problem in words.

Too often, programmers will turn to writing code before thinking critically about the problem at hand. Not good. One strategy for firing up your brain before you touch the keyboard is using words, English or otherwise, to describe the sub-problem that you have identified within the original problem.

If you’re solving a problem that requires dynamic programming, grab a piece of paper and think about the information that you need to solve this problem. Write out the sub-problem with this in mind.

For example, in the punchcard problem, I stated that the sub-problem can be written as “the maximum value schedule for punchcards i through n such that the punchcards are sorted by start time.” I found this sub-problem by realizing that, in order to determine the maximum value schedule for punchcards 1 through n such that the punchcards are sorted by start time, I would need to find the answer to the following sub-problems:

• The maximum value schedule for punchcards n-1 through n such that the punchcards are sorted by start time
• The maximum value schedule for punchcards n-2 through n such that the punchcards are sorted by start time
• The maximum value schedule for punchcards n-3 through n such that the punchcards are sorted by start time
• (Et cetera)
• The maximum value schedule for punchcards 2 through n such that the punchcards are sorted by start time

If you can identify a sub-problem that builds upon previous sub-problems to solve the problem at hand, then you’re on the right track.

Step 2: Write out the sub-problem as a recurring mathematical decision.

Once you’ve identified a sub-problem in words, it’s time to write it out mathematically. Why? Well, the mathematical recurrence, or repeated decision, that you find will eventually be what you put into your code. Besides, writing out the sub-problem mathematically vets your sub-problem in words from Step 1. If it is difficult to encode your sub-problem from Step 1 in math, then it may be the wrong sub-problem!

There are two questions that I ask myself every time I try to find a recurrence:

• What decision do I make at every step?
• If my algorithm is at step i, what information would it need to decide what to do in step i+1? (And sometimes: If my algorithm is at step i, what information did it need to decide what to do in step i-1?)

Let’s return to the punchcard problem and ask these questions.

What decision do I make at every step? Assume that the punchcards are sorted by start time, as mentioned previously. For each punchcard that is compatible with the schedule so far (its start time is after the finish time of the punchcard that is currently running), the algorithm must choose between two options: to run, or not to run the punchcard.

This dynamic program chooses between two options at each step, just like our dear friend Hamlet!

If my algorithm is at step i, what information would it need to decide what to do in step i+1? To decide between the two options, the algorithm needs to know the next compatible punchcard in the order. The next compatible punchcard for a given punchcard p is the punchcard q such that _sq (the predetermined start time for punchcard q) happens after _fp (the predetermined finish time for punchcard p) and the difference between _sq and _fp is minimized. Abandoning mathematician-speak, the next compatible punchcard is the one with the earliest start time after the current punchcard finishes running.

If my algorithm is at step i, what information did it need to decide what to do in step i-1? The algorithm needs to know about future decisions: the ones made for punchcards i through n in order to decide to run or not to run punchcard i-1.

Now that we’ve answered these questions, perhaps you’ve started to form a recurring mathematical decision in your mind. If not, that’s also okay, it becomes easier to write recurrences as you get exposed to more dynamic programming problems.

Without further ado, here’s our recurrence:

OPT(i) = max(v_i + OPT(next[i]), OPT(i+1))

This mathematical recurrence requires some explaining, especially for those who haven’t written one before. I use OPT(i) to represent the maximum value schedule for punchcards i through n such that the punchcards are sorted by start time. Sounds familiar, right? OPT(•) is our sub-problem from Step 1.

In order to determine the value of OPT(i), we consider two options, and we want to take the maximum of these options in order to meet our goal: the maximum value schedule for all punchcards. Once we choose the option that gives the maximum result at step i, we memoize its value as OPT(i).

The two options — to run or not to run punchcard i — are represented mathematically as follows:

v_i + OPT(next[i])

This clause represents the decision to run punchcard i. It adds the value gained from running punchcard i to OPT(next[i]), where next[i] represents the next compatible punchcard following punchcard i. OPT(next[i]) gives the maximum value schedule for punchcards next[i] through n such that the punchcards are sorted by start time. Adding these two values together produces maximum value schedule for punchcards i through n such that the punchcards are sorted by start time if punchcard i is run.

OPT(i+1)

Conversely, this clause represents the decision to not run punchcard i. If punchcard i is not run, its value is not gained. OPT(i+1) gives the maximum value schedule for punchcards i+1 through n such that the punchcards are sorted by start time. So, OPT(i+1) gives the maximum value schedule for punchcards i through n such that the punchcards are sorted by start time if punchcard i is not run.

In this way, the decision made at each step of the punchcard problems is encoded mathematically to reflect the sub-problem in Step 1.

Step 3: Solve the original problem using Steps 1 and 2.

In Step 1, we wrote down the sub-problem for the punchcard problem in words. In Step 2, we wrote down a recurring mathematical decision that corresponds to these sub-problems. How can we solve the original problem with this information?

OPT(1)

It’s that simple. Since the sub-problem we found in Step 1 is the maximum value schedule for punchcards i through n such that the punchcards are sorted by start time, we can write out the solution to the original problem as the maximum value schedule for punchcards 1 through n such that the punchcards are sorted by start time. Since Steps 1 and 2 go hand in hand, the original problem can also be written as OPT(1).

Step 4: Determine the dimensions of the memoization array and the direction in which it should be filled.

Did you find Step 3 deceptively simple? It sure seems that way. You may be thinking, how can OPT(1) be the solution to our dynamic program if it relies on OPT(2), OPT(next[1]), and so on?

You’re correct to notice that OPT(1) relies on the solution to OPT(2). This follows directly from Step 2:

OPT(1) = max(v_1 + OPT(next[1]), OPT(2))

But this is not a crushing issue. Think back to Fibonacci memoization example. To find the Fibonacci value for n = 5, the algorithm relies on the fact that the Fibonacci values for n = 4, n = 3, n = 2, n = 1, and n = 0 were already memoized. If we fill in our memoization table in the correct order, the reliance of OPT(1) on other sub-problems is no big deal.

How can we identify the correct direction to fill the memoization table? In the punchcard problem, since we know OPT(1) relies on the solutions to OPT(2) and OPT(next[1]), and that punchcards 2 and next[1] have start times after punchcard 1 due to sorting, we can infer that we need to fill our memoization table from OPT(n) to OPT(1).

How do we determine the dimensions of this memoization array? Here’s a trick: the dimensions of the array are equal to the number and size of the variables on which OPT(•) relies. In the punchcard problem, we have OPT(i), which means that OPT(•) only relies on variable i, which represents the punchcard number. This suggest that our memoization array will be one-dimensional and that its size will be n since there are n total punchcards.

If we know that n = 5, then our memoization array might look like this:

memo = [OPT(1), OPT(2), OPT(3), OPT(4), OPT(5)]

However, because many programming languages start indexing arrays at 0, it may be more convenient to create this memoization array so that its indices align with punchcard numbers:

memo = [0, OPT(1), OPT(2), OPT(3), OPT(4), OPT(5)]

Step 5: Code it!

To code our dynamic program, we put together Steps 2–4. The only new piece of information that you’ll need to write a dynamic program is a base case, which you can find as you tinker with your algorithm.

A dynamic program for the punchcard problem will look something like this:

def punchcardSchedule(n, values, next): # Initialize memoization array - Step 4  memo = [0] * (n+1)   # Set base case  memo[n] = values[n]   # Build memoization table from n to 1 - Step 2  for i in range(n-1, 0, -1):    memo[i] = max(v_i + memo[next[i]], memo[i+1])  # Return solution to original problem OPT(1) - Step 3  return memo[1]

Congrats on writing your first dynamic program! Now that you’ve wet your feet, I’ll walk you through a different type of dynamic program.

Paradox of Choice: Multiple Options DP Example

Unrelated to DP, but an accurate depiction of how harrowing multi-option decisions can be.

Although the previous dynamic programming example had a two-option decision — to run or not to run a punchcard — some problems require that multiple options be considered before a decision can be made at each step.

Time for a new example.

Pretend you’re selling the friendship bracelets to n customers, and the value of that product increases monotonically. This means that the product has prices {_p1, …, _pn} such that _p_i ≤ pj if customer j comes after customer i. These n customers have values {_v1, …, _vn}. A given customer i will buy a friendship bracelet at price _pi if and only if _pi ≤ _vi; otherwise the revenue obtained from that customer is 0. Assume prices are natural numbers.

Problem: You must find the set of prices that ensure you the maximum possible revenue from selling your friendship bracelets.

Take a second to think about how you might address this problem before looking at my solutions to Steps 1 and 2.

Step 1: Identify the sub-problem in words.

Sub-problem: The maximum revenue obtained from customers i through n such that the price for customer i-1 was set at q.

I found this sub-problem by realizing that to determine the maximum revenue for customers 1 through n, I would need to find the answer to the following sub-problems:

• The maximum revenue obtained from customers n-1 through n such that the price for customer n-2 was set at q.
• The maximum revenue obtained from customers n-2 through n such that the price for customer n-3 was set at q.
• (Et cetera)

Notice that I introduced a second variable q into the sub-problem. I did this because, in order to solve each sub-problem, I need to know the price I set for the customer before that sub-problem. Variable q ensures the monotonic nature of the set of prices, and variable i keeps track of the current customer.

Step 2: Write out the sub-problem as a recurring mathematical decision.

There are two questions that I ask myself every time I try to find a recurrence:

• What decision do I make at every step?
• If my algorithm is at step i, what information would it need to decide what to do in step i+1? (And sometimes: If my algorithm is at step i, what information would it need to decide what to do in step i-1?)

Let’s return to the friendship bracelet problem and ask these questions.

What decision do I make at every step? I decide at which price to sell my friendship bracelet to the current customer. Since prices must be natural numbers, I know that I should set my price for customer i in the range from q — the price set for customer i-1 — to _vi — the maximum price at which customer i will buy a friendship bracelet.

If my algorithm is at step i, what information would it need to decide what to do in step i+1? My algorithm needs to know the price set for customer i and the value of customer i+1 in order to decide at what natural number to set the price for customer i+1.

With this knowledge, I can mathematically write out the recurrence:

OPT(i,q) = max~([Revenue(v_i, a) + OPT(i+1, a)])

such that max~ finds the maximum over all a in the range q ≤ a ≤ v_i

Once again, this mathematical recurrence requires some explaining. Since the price for customer i-1 is q, for customer i, the price a either stays at integer q or it changes to be some integer between q+1 and _vi. To find the total revenue, we add the revenue from customer i to the maximum revenue obtained from customers i+1 through n such that the price for customer i was set at a.

In other words, to maximize the total revenue, the algorithm must find the optimal price for customer i by checking all possible prices between q and _vi. If _vi ≤ q, then the price a must remain at q.

What about the other steps?

Working through Steps 1 and 2 is the most difficult part of dynamic programming. As an exercise, I suggest you work through Steps 3, 4, and 5 on your own to check your understanding.

Runtime Analysis of Dynamic Programs

Now for the fun part of writing algorithms: runtime analysis. I’ll be using big-O notation throughout this discussion . If you’re not yet familiar with big-O, I suggest you read up on it here.

Generally, a dynamic program’s runtime is composed of the following features:

• Pre-processing
• How many times the for loop runs
• How much time it takes the recurrence to run in one for loop iteration
• Post-processing

Overall, runtime takes the following form:

Pre-processing + Loop * Recurrence + Post-processing

Let’s perform a runtime analysis of the punchcard problem to get familiar with big-O for dynamic programs. Here is the punchcard problem dynamic program:

def punchcardSchedule(n, values, next): # Initialize memoization array - Step 4  memo = [0] * (n+1)   # Set base case  memo[n] = values[n]   # Build memoization table from n to 1 - Step 2  for i in range(n-1, 0, -1):    memo[i] = max(v_i + memo[next[i]], memo[i+1])  # Return solution to original problem OPT(1) - Step 3  return memo[1]

Let’s break down its runtime:

• Pre-processing: Here, this means building the the memoization array. O(n).
• How many times the for loop runs: O(n).
• How much time it takes the recurrence to run in one for loop iteration: The recurrence takes constant time to run because it makes a decision between two options in each iteration. O(1).
• Post-processing: None here! O(1).

The overall runtime of the punchcard problem dynamic program is O(n) O(n) * O(1) + O(1), or, in simplified form, O(n).

You Did It!

Well, that’s it — you’re one step closer to becoming a dynamic programming wizard!

Margaret Hamilton: one of the many programming wizards in our history!

One final piece of wisdom: keep practicing dynamic programming. No matter how frustrating these algorithms may seem, repeatedly writing dynamic programs will make the sub-problems and recurrences come to you more naturally. Here’s a crowdsourced list of classic dynamic programming problems for you to try.

So get out there and take your interviews, classes, and life (of course) with your newfound dynamic programming knowledge!

Many thanks to Steven Bennett, Claire Durand, and Prithaj Nath for proofreading this post. Thank you to Professor Hartline for getting me so excited about dynamic programming that I wrote about it at length.

Enjoy what you read? Spread the love by liking and sharing this piece. Have thoughts or questions? Reach out to me on Twitter or in the comments below.