Simple Framework for Solving Dynamic Programming Problems

4 min readNov 6, 2020

Dynamic programming problems! If you’re studying for coding interviews, dynamic programming is a common term that scares a lot of people, but it doesn’t have to be! I hope with this article I can at least make it a little less confusing 😀.

Today I’ll be describing a framework for solving dynamic programming problems. It’s more easily explained using an example.

🚶‍♂️ Climbing Stairs Problem

The basic question is as follows: We’re given a staircase of size N steps, and the constraint is that we can climb either 1 or 2 steps at a time. Find the total number of ways to get to the top of the staircase.

So how do we solve this problem?

The first thing we need to do is express our goal as an objective function.

What is an objective function? An objective function is the function that you want to minimize or maximize in your problem.

In this case, the objective function is the distinct number of ways to reach the i-th stair. So this is a minimization problem.

Let’s say F(i) is the number of distinct ways to reach the i-th stair. The definition of the objective function is usually in the problem description itself. This is the framework we will take for solving DP problems:

Step 1: Write down the objective function.

Step 2: Break the problem down into simpler sub-problems and identify the base cases. DP is always about breaking down the problem into simpler subproblems.

But how do you do that? What we can usually do is break the problem down into such small sub problems that a computer isn’t even needed.

If we solve this problem for when we only have 2 steps. So F(2), how many distinct ways exist to get to the second stair? Since we can only make 1 or 2 steps at a time, we can either make 2x1 steps or 1x2 step, so there are only 2 distinct ways to satisfy F(2).

F(2) = 2.

Let’s calculate F(1).

F(1)=1. We can only take one step to reach step 1.

The smallest subproblem is actually when we don’t have a staircase at all! F(0).

So how many distinct ways are there to reach F(0), there is only 1! Doing nothing.

So now we have:

If we would solve this problem for F(3) , F(4), and F(5) we might then see a pattern. But how would we go about solving this problem? If we are at the top of the staircase at step N, let’s ask ourselves: how could we get here? Since we know we can make either 1 or 2 steps at a time, we could get here either from the N-1 stair or the N-2 stair, and that’s it; we can’t get there from anywhere else!

So how do we know how many distinct ways? We have to add F(n-1) + F(n-2). In combinatorics, this is called the rule of sum or addition principle. Basically, it means if we have A ways of doing something and B ways of doing another thing, and we can’t do both things at the same time, then there are A + B ways to choose one of the actions. In our case we always choose to either make 1 step or 2 steps, so that’s why it applies.

Let’s do this following the framework:

1. Define the objective function

2. Identify base cases (sub problems)

3. Recurrence relation

This is a new step! This is the transition function. It allows you to transition from one subproblem to the other subproblem

4. Order of computation

Means we need to determine the order in which subproblems are solved. In this case we are relying on n-1 and n-2, so we need to calculate smaller n values first.

5. Location of the answer

Implementation

"""
Problem
 Climbing StairsYou are climbing a stair case. It takes n steps to reach the top.
  Each time you can either climb 1 or 2 steps.
 How many distinct ways can you climb to the top?Framework for solving DP problems:
 1. Define the objective function
   f(i) is the number distinct ways to reach the i-th stair.
 2. Identify base cases
   f(0) = 1
   f(1) = 1
 3. Write down a recurrence relation for the optimized objective function
   f(n) = f(n-1) + f(n-2)
 4. What's order of execution?
   Bottom-up, because we always rely on values from 2 previous sub-problems
 5. Where to look for the answer?
   f(n)
"""# Time complexity: O(n) | Space complexity: O(n)
def climbStairs(n):
    ways = [0 for i in range(0, n + 1)]
    ways[0] = 1
    ways[1] = 1
    for i in range(2, len(ways)):
        ways[i] = ways[i - 1] + ways[i - 2]
    return ways[i]

The time complexity of this function is O(n) because we have to iterate over all the steps, and the space is also O(n) because we create an array to cache the values.

And that’s pretty much it! Following this framework makes these types of problems much less intimidating ☺️