DP — Introduction to Dynamic Programming: Part 2

Sethuram.S.V

5 min readAug 3, 2021

“Those who do not remember the past are condemned to repeat it.”

The quote is from George Santayana, captures the essence of dynamic programming. DP is all about remembering the results of the sub-problems that we have already solved, and not solving them again. This time around, we’ll learn about the bottom-up approach of dynamic programming and strengthen our skills in identifying the overlapping subproblems and optimal substructure property of a problem. Just like last time around, we’ll seek the help of an example to learn the concepts.

Note

This is the continuation of my last blog where I detail the characteristics of dynamic programming with the Fibonacci sequence as an example and solved it using the top-down approach.

DP — Introduction to Dynamic Programming: Part 1

Dynamic programming is an algorithmic approach for solving an optimization problem by breaking it down into simpler…

sethuram52001.medium.com

This time around I have taken the example of Pascal’s triangle:

Pascal’s triangle is a triangular array constructed by summing adjacent elements in the preceding rows. Pascal’s triangle contains the values of the binomial coefficients, it helps us visualize many properties of the binomial coefficient and the binomial theorem.

So, if you’re familiar with Pascal’s identity,

ⁿCᵣ = ⁿ ⁻ ¹Cᵣ ₋ ₁ + ⁿ ⁻ ¹Cᵣ

you can code the problem as the following. It’s pretty simple logic to generate Pascal’s triangle. We’re using the fact that the values in Pascal’s triangle can be represented in combinatorics form, then we can use Pascal’s identity to compute the values using a recursive function.

If you try it run the program for smaller values of n it sure runs fine, but do try it running it for like n = 1000, you may notice the lag, it’s because of the time complexity of the above code is exponential, the recursive binomial function based on Pascal’s identity is O(2ⁿ) in itself, but you could optimize the binomial function and bring down the overall time complexity down to O(n³).

But let’s not be carried away with the binomial theorem concept of pascal’s triangle. I took this particular example for the property of pascal’s triangle, that each value in the row can be obtained by summing the adjacent elements in the preceding row.

This leads to us the characteristic of DP, the optimal substructure property:

triangle[r][c] = triangle[r - 1][c - 1] + triangle[r - 1][c]

We can say a problem has optimal substructure property if its overall optimal solution can be obtained from the optimal solutions of its subproblems. To put in context, as we see in Pascal’s triangle, each row can be constructed by using the adjacent values present in its previous row.

The algorithm we discussed is a brute algorithm, but it helps us trace out another characteristic of a DP-based problem: overlapping subproblems. Below is the recursion tree for the binomial function in our algorithm, where you could notice that many recursive calls are repeated across branches.

Recursion tree of the binomial function based on Pascal’s identity

So, the overlapping subproblems characteristic is nothing but when a recursive algorithm repeatedly visits the same subproblems.

Okay, let’s take a break from the terminologies of DP and return to the problem at the hand. The intuition is simple, if we have a row of Pascal’s triangle, we can easily compute the next row by each pair of adjacent values present in the previous row.

Although the algorithm is very simple, the iterative approach to constructing Pascal’s triangle can be classified as DP because we construct each row based on the previous row. First, we generate the overall triangle list, which will store each row as a sublist. Since the number of rows is a natural number we can initialize the triangle with [1] as its first row, and proceed to fill the rows as per the optimal substructure property. And every row’s first and last value is always 1, so we append 1 at the beginning and end of each row.

Well, this method of solving the problem is called tabulation. To put in context, we tabulate the results of each row using the help of ArrayList over here (usually it’s an n-dimensional array), now we use these values to calculate the next value of an element in the next row instead of blindly computing the binomial coefficient value.

Tabulation is another method available in DP to solve a problem. This is called the bottom-up approach as we try to solve the sub-problems first to obtain the solution for the original problem.

A quick comparison between Memoization and Tabulation

Memoization is generally easier to code compared to a tabulation. Coming up with a specific order while dealing with a lot of conditions might be difficult in tabulation, whereas those problems are easily solved using conditional statements in memoization.
However, tabulation avoids the memory problems, as going bottom-up avoid the recursion, saving the memory cost that recursion builds up in the call stack.

Quick Recap

We strengthened our skills in identifying the characteristic of dynamic programming — a) overlapping subproblems and b) optimal substructure, with the help of Pascal’s triangle problem.
We saw about the bottom-up approach with tabulation of dynamic programming, where we use the help of previously solved subproblems to solve the original problem. Using a table, combine the solution of the smaller subproblems and eventually solve to complete the problem.

So, we have come to the end of this post, and thank you so much 😊 if you have made it this far into this post. I will see you in my next post with some general problems based on DP.