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 rodCutting(n, prices):
  if n<0:
    return 0
  max_val = 0
  for i in range(1,n+1):
      max_val = max(max_val, prices[i-1] + rodCutting(n - i, prices))
  return max_val

print(rodCutting(3, [3,7,8]))

## Explanation

The idea of this algorithm is to exhaustively find the most optimal cuts from every combination of cuts. We do this by making recursive calls with all possible values of length and choosing those that give us the highest revenue (*lines 5-7*).


The crux of this algorithm is in *line 6*. We make recursive calls for each possible length of the piece (`i`); the updated value of `n` now is `i` units smaller. Once this result is evaluated, we add this length’s price and find the `max`.




The visualization below shows a dry run of this algorithm.



## Time complexity

Can you think of the number of combinations of cuts for a rod of length *n*? It is $2^{n-1}$! For a rod of length $n$, at each position, we have two choices. Either we can make a cut, or we can leave it as it is. All combinations are bounded by O(2^n) as is the time complexity of this solution.

# Solution 2: Top-down dynamic programming

Let's see if this problem satisfies both the properties of dynamic programming.

## Optimal substructure

We want to find the optimal answer for a rod of length n, and we have optimal answers to all the subproblems, i.e., rods of length *n-1*, *n-2*, … , *2*, *1*. We can find the maximum of all the subproblem's results plus the price of the rod length that remains along with that subproblem. The following would be the equation for finding the optimal cut's revenue for a rod of length *n*.

$$RC(n) = max (RC(n-1) + price(1) , RC(n-2) + price(2) \ \ ... \ \ RC(1) + price(n-1))$$

Thus, if we have answers to the subproblems of rods of length *n-1*, *n-2* ... *2* and *1*, we can construct the solution for the rod of length *n* by only using these results. 

## Overlapping subproblems

By looking at the visualization above, you can already see one overlapping subproblem. For bigger inputs, this overlap will increase substantially.


In this lesson, we will look at different algorithms to solve the rod cutting problem we saw in the 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 Rod Cutting Problem

Solution 1: Simple recursion #

Explanation

Time complexity