Gain insights into dynamic programming, explore recursion basics, and delve into advanced techniques like Bottom-Up optimization. Discover ways to solve complex problems more efficiently with hands-on coding challenges.

Dynamic programming is something every developer should have in their toolkit. It allows you to optimize your algorithm with respect to time and space — a very important concept in real-world applications.

In this course, you’ll start by learning the basics of recursion and work your way to more advanced DP concepts like Bottom-Up optimization. Throughout this course, you will learn various types of DP techniques for solving even the most complex problems. Each section is complete with coding challenges of varying difficulty so you can practice a wide range of problems.

By the time you’ve completed this course, you will be able to utilize dynamic programming in your own projects.

Dynamic Programming in Python: Optimizing Programs for Efficiency

def staircase(n, m):
  # base case of when there is no stair
  if n == 0:    
    return 1
  ways = 0
  # iterate over number of steps, we can take
  for i in range(1,m+1):  
    # if steps remaining is smaller than the jump step, skip   
    if i <= n:  
      # recursive call with n i units lesser where i is the number of steps taken here            
      ways += staircase(n-i, m) 
  return ways

print(staircase(4,2))

## Explanation

The problem is similar to the Fibonacci numbers algorithm. Instead of binary recursion, we have an m-ary recursion here. Which means every recursive makes, at most, m recursive calls. 

The algorithm is pretty intuitive as well. At any step, we have the option to take steps of `m` different lengths, i.e., we can either take `1` step, `2` steps, or so on up to `m` steps. Each different step will result in a different path. Therefore, we make recursive calls with each number of steps (from `1` to `m`). We subtract `i` from n for each call since we have taken `i` number of steps at this instance (*lines 7-11*). Our algorithm will conclude when `n` becomes equal to `0`. This would mean we have reached the top of the staircase, and the path we took to get there constitutes one of the many paths, therefore we will return 1 here (*lines 3-4*). This is our base case. Look at the following visualization for a dry run of this algorithm.



## Time complexity
Every time we can make up to `m` recursive calls. `m` recursive calls from `m` recursive calls and so on results in exponential time complexity. That means $m \times m \times m...m = m^n$, this time complexity is **O(m$^n$)**.


# Dynamic programming properties

Notice how this problem satisfies both conditions of dynamic programming.

## Optimal substructure

If we want to evaluate the answer for `staircase(n, m)`, and we have answers for `staircase(n-1, m)`, `staircase(n-2, m)`, ... `staircase(n-m, m)`, we can simply sum up all these answers to get the answer for the `staircase(n, m)`.

## Overlapping subproblems

Notice how `staircase(n-2, m)` will appear as a subproblem of `staircase(n, m)` and `staircase(n-1, m)`.

If you look at the final slide, there are some repeating sub-problems. Can you identify them?

If we have come two steps up the staircase, we know there are only two ways to take the next two steps. Thus the call `staircase(2,2)` will always evaluate to `2`. We are reevaluating it two times. The same is the case for the call `staircase(3,2)`, we are re-evaluating it three times. 



In this lesson, we will review the staircase problem from the coding challenge in last lesson.

Chapter 1: From Recursion to Dynamic Programming

Chapter 2: Top-Down Dynamic Programming with Memoization

Chapter 3: Bottom-Up Dynamic Programming with Tabulation

Chapter 4: Practice Problems

Solution Review: The Staircase Problem

Solution 1: Simple recursion

Explanation