Dissecting Dynamic Programming — Recurrence Relation
From the previous blog (Top Down & Bottom Up), we learned the essence of solving Dynamic Programming problems is to derive the recurrence relation, and then use either the top-down or bottom-up approach to translate it to code. Therefore it is important to master the problem analysis and the techniques to derive a recurrence relation. This blog and the future ones will focus on sharing the insights to help with this.
This blog will use a simple (level 1) Dynamic Programming problem called Climbing Stairs to illustrate the problem analysis and the techniques at arriving at a recurrence relation.
Here is the problem statement:
You are climbing a staircase. It takes
nsteps to reach the top.Each time you can either climb
1or2steps. In how many distinct ways can you climb to the top?Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 stepsExample 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
Problem Analysis:
- This problem has only 1 input, which represents the number of steps a staircase has
- There are only two choices (ways) to climb the staircase — 1 or 2 steps at a time
- What does “distinct ways to climb to the stop” means? If we analyze the examples closely, a distinct way to climb to the top of a staircase means the combination of climbing either 1 or 2 steps from the bottom to the top of the staircase. In other words, when the sum of the steps in each combination equals to the number of steps the staircase has. There are many different combinations and each one is counted as 1 distinct way. The final answer is the sum of all the different combinations.
- Where do the combinations come from? They come from taking a series choices repeatedly while climbing to the top of the staircase (See Figure #1). In other words, each combination consists of a series choices (1 or 2 steps). As a climber lands on a particular step, at that point, the climber has to choices to go from there, either take 1 step or 2 steps. In order to count the total number of distinct ways, the climber will try both.
- We start with n steps in a staircase, as we repeatedly climb using either 1 or 2 steps, how does the problem gets smaller? If we climb 1 step then the problem becomes 1 step (n-1) smaller, and if we climb 2 steps then the problem becomes 2 steps (n-2) smaller. In other words, as we climb more steps, the problem (remaining steps to climb) becomes smaller and smaller until until there are no more steps to climb (reaching the top of the staircase)
- How do we know when to stop climbing? Either when there are no more steps to climb (n=0, we are at the top of the staircase), or the remaining steps is smaller than the number of steps that we are planning to take.
Problem Breakdown Tree:
Another way to visualize the problem analysis described above is to use Figure #2. Let’s say our staircase has 4 steps. As we climb it by taking 1 or 2 steps, the number of remaining steps is getting smaller. At each point, we have two choices (1 step or 2 steps) to climb and that is represented by the branching out of each node. Starting from the top node (root), each path goes all the way down to a node with a value of 0 represents a distinct way of climbing to the top. For a staircase of 4 steps, there are 5 distinct ways of climbing to the top.
Formalize Recurrence Relation:
Figure #3 depicts how the total number of distinct ways to climb a staircase is computed. For example, when a staircase has 4 steps, the total number of distinct ways to climb to the top is 5, which is the sum of the total number of distinct ways to climb a staircase that has 3 steps and total number of distinct ways to climb a staircase that has 2 steps.
If we use function f(4) to represent the total number of distinct ways to climb a staircase, then it would be f(4) = f(3) + f(2). Each part of the right side of the function represents a particular choice specified in the problem statement above.
To generalize the recurrence relation a bit, we just need to substitute the value 4 with a variable called n, then f(n) = f(n-1) + f(n-2). To complete the recurrence relation, we need to figure out the base case(s). Looking at the leaf nodes in Figure #3, that should give us sufficient info. to determine the base case is f(0) = 1.
Recurrence relation: f(n) = f(n-1) + f(n-2) and f(0) = 1
Wrapping Up:
The recurrence relation for the climbing stairs problem is extremely similar to the one for Fibonacci sequence. There is one small difference, which is the base case.
Given the similarity, I will leave it as an exercise for the readers to translate the recurrence relation above to code. Feel free to refer the previous blog “Top Down & Bottom Up” for the code and the complexity and runtime analysis.
Summary:
Coming up with a recurrence relation requires:
- A rigorous analysis of the problem statement, a thorough understanding the given choices to explore the subproblems
- Work through the examples of smaller problem size to formalize the problem understanding
- Draw up the problem breakdown tree to visualize the subproblems, their relationship and to verify they meet the Dynamic Programming properties (Optimal Substructure and Overlapping subproblems)
- Formalize the recurrence relation for a specific small problem size, then generalize it and finally identify the base case(s)
As a challenge for the readers, go and apply the learning from this blog to solve a very similar Dynamic Programming problem called “Unique Paths”.
Future blogs will dissect more challenging Dynamic Problems.
It will be a fun exercise to build up a table of Dynamic Programming problems and the associated recurrence relations.
Have fun and do let me know if there are Dynamic Problems that you would me to dissect in the future blogs.
