A collection of algorithms for problems using dynamic programming

• Dynamic Programming — An introduction
• Dynamic Programming — Maximum Contiguous Subsequence Sum
• Dynamic Programming — Longest Increasing Subsequence

Let us find the longest increasing subsequence using dynamic programming.

We are going to solve yet another DP problem using the strategies we discussed in the previous post. If you haven’t, I strongly recommend you read my introduction post here, so it is easy to follow the slang.

Problem Definition (DPV, chapter 6.2)

We are given an array of numbers. A subsequence is a subset of these numbers taken in order, they can be consecutive or non-consecutive. An increasing subsequence is where the numbers are getting strictly larger. Our goal here is to find the length of the longest increasing subsequence.

Example: A = [5, -3, 7, 1, 10, 2, 3, -8]. Subsequence here are [5, 2, -8], [-3, 7, 1], [5, -8], etc. Increasing subsequences here are [5, 7, 10] , [2, 3],etc.

Input: Array of n numbers A = a1, a2,…. an

Output: Length of longest increasing subsequence.

Solution

From this, let us identify the recurring theme and crack the questions.

L[i] = Length of the maximum increasing subsequence until ith position, ending with element A[i].

At last, we find the output by finding at which position i, maximum length was yielded. (Note: The max length need not always be at the last position. In our example, it is at i=6, LIS length = 4, LIS = [-3, 1, 2, 3].

Algorithm

Time complexity : O(n²)

Footnote: If you still don’t get DP don’t worry, Sheldon Cooper wouldn’t get it in his first try! Keep on reading, practicing and asking questions!

Citations:

Dasgupta, Sanjoy, et al. Algorithms. McGraw-Hill Higher Education, 2008.

Let us find the maximum sum yielded by a contiguous subsequence using dynamic programming.

If you have not already, I highly recommend reading the introduction to Dynamic Programming here.

Problem definition (DPV, Chapter 6.1)

A contiguous subsequence of a list S is a subsequence made up of consecutive elements of S.

For instance, if S is: 5, 15, -30, 10, -5, 40, 10 . Then 15, -30, 10 is a contiguous subsequence but 5, 15, 40 is not.

Input: A list of numbers, a1, a2, …, an

Output: The contiguous subsequence with the maximum sum and the sum (a subsequence of length zero has sum zero)

For the preceding example, the answer would be 10, -5, 40, 10, with a sum of 55.

Let’s brute force the bits and bytes out of it!

We iterate over each element, iterate over the rest and find the sum of the subsequences, finding the maximum of all.

The time complexity is through the roof, and who wants O(n^2) if we can do linear ?

Dynamic Programming to the rescue

As always,

1. Let’s place our input and output arrays on the saucepan.
2. Find the optimal solution at that juncture.
3. Ask THE perfect questions (secret ingredient)!
4. Trust the guys before us with our life and turn off the stove.

From this, we can identify the recurring theme and crack the questions.

Let us define, S[i] = Maximum sum yielded by contiguous subsequence until ith position, ending with element A[i].

At last, we find the output by finding at which position i, maximum sum was yielded. (Note: The max sum need not always be at the last position. Imagine instead of A[n] = 10, what if it was A[n] = -5, S[n] would be 40. Then the overall max sum is 45, yielded by {10, -5, 40}, ending at i=5)

And that’s solving maximum contiguous subsequence sum in O(n) linear time, done and dusted.

Citations:

Dasgupta, Sanjoy, et al. Algorithms. McGraw-Hill Higher Education, 2008.

Are you intimidated by dynamic programming? Then this post will help you ask out DP for a cup of coffee!

Dynamic programming or DP is a household name for Computer Science students. It is tagged as one of the most difficult algorithmic techniques to learn and naturally is one heavily weighted topic in Algorithm courses. So, no wonder students curse DP!

So, what is with all the hype with Dynamic Programming?

It is an algorithmic technique where you solve a complex problem, by breaking it down into smaller sub-problems, and then find optimal solutions which would lead us to the optimal solution for the larger problem. At least, this is what it is according to Wikipedia.

But what I learned behind all this jargon?

I found that the foundation for DP is TRUST! Its not the regular trust. In the world of DP, as a sub-problem, you are trusting the guy before you as if your life depended on it!

However, it doesn’t end there, there is one more secret ingredient attached. Read more to find out!

Let us look at an effortless example to understand trust here!

There is a problem at hand, where we are supposed to construct a humungous(miles long!) perfect square. Imagine, I decide to break this down, out of the assumption that if I can make a 100 perfect small squares, keep joining them together and make bigger ones and at last I will get my one Bigg square.

Do you see where I am getting to? If I were to say with 100% confidence that the large square(complex problem) is THE perfect one, it means I trust the smaller guys(sub-problems) that make up this square to be perfect(optimal) ones! See, how I cleverly injected the jargon back!

Let us dive into an actual DP problem!

Finding the nth Fibonacci number

Every number in the Fibonacci sequence except the first two, can be given by the sum of the previous two numbers.

Eg: 0, 1, 1(0+1), 2(1+1), 3(1+2), 5(2+3), 8(3+5), 13(5+8)…

Here, we have broken the task into smaller sub-problems where we iteratively calculate from 1 until n. When we reach n, all we need is n-1 and n-2. n is trusting his peers n-1 and n-2 that they did their job optimally of finding Fib(n-1) and Fib(n-2) and now that he can use their solution to give his final optimal solution Fib(n).

The secret ingredient!

Though we trust the previous guys to have done their job well, they have found the optimal solution until their point. But that need not be what is right when we have to figure out what is best for us. So, we ask questions!

For every DP problem that I have solved until now, I did so only because I was able to crack THE perfect question(s) to ask! Cracking that is all that matters, the rest will follow you to your grave.

Whenever you’re struggling to crack the question, remember,