Dissecting Dynamic Programming — Recurrence Relation

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.
Figure #1 — choices of climbing a staircase
  • 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:

Figure #2 — visualization of problem breakdown tree

Formalize Recurrence Relation:

Recurrence relation: f(n) = f(n-1) + f(n-2) and f(0) = 1

Figure #3 — visualization of recurrence relation

Wrapping Up:

Summary:

  • 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)

Previous Blogs:

Resources:

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store