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

# Dynamic programming, the magic wand

Do you remember the run time complexity of the Fibonacci algorithm from [earlier lessons](https://www.educative.io/courses/dynamic-programming-in-python/is-plain-recursion-good-enough#recursions-inefficiency-visualized)? We even saw how bad that algorithm performed as we tried to calculate a slightly higher (~50) Fibonacci number. We have modified that algorithm to remember the values it has already evaluated to avoid re-evaluations. Run this code with different values to see how much time the algorithm takes. For comparison, we have reproduced the simple recursion-based solution below as well as in the other tab.


import time
import matplotlib.pyplot as plt

calculated = {}

def fib(n):
  if n == 0: # base case 1
    return 0
  if n == 1: # base case 2
    return 1
  elif n in calculated:
    return calculated[n]
  else: # recursive step
    calculated[n] = fib(n-1) + fib(n-2)
    return calculated[n]

showNumbers = True
numbers = 20

DynamicProgrammingSolution

import time
import matplotlib.pyplot as plt

def fib(n):
  if n <= 0: # base case 1
    return 0
  if n <= 1: # base case 2
    return 1
  else: # recursive step
    return fib(n-1) + fib(n-2)

numbers = 20

SimpleRecursion

Magical! Look at the almost linear time complexity curve formed now instead of an exponential curve. Try updating the value now with numbers as big as 500. When trying bigger numbers, set the `showNumbers` variable to `False` so that the graph does not become messy. This is just a primer of how wonderful dynamic programming is. We are going to discuss the Fibonacci numbers example in depth in later chapters.



# Dynamic programming, the 'selective' magic wand

As amazing as dynamic programming is, you cannot use it on every kind of problem. There are a number of problems that entail an exponential complexity, but their complexity cannot be reduced even after using dynamic programming. In fact, a problem needs to meet very strict prerequisites before it can be solved using dynamic programming. These prerequisites are **optimal substructure** and **overlapping subproblems**. 

# Optimal substructure

This property means that an optimal solution to a problem can be built using the optimal solutions to that problem’s subproblems. Essentially, we should be able to specify the problem in terms of its subproblems in such a way that if we know the optimal answer to the subproblem, the evaluation of the problem can simply use that answer. This might seem straightforward, but it is a little tricky. Let’s look at two examples to see what we mean.


## Count characters in a string

We saw this [problem](https://www.educative.io/courses/dynamic-programming-in-python/thinking-recursively#coding-exercise) in the second lesson of this course where we were counting characters in a string. Let’s say we already know there are `k` number of `char`s in the string of length `n`. If we were to construct another string by appending a character to `str`, we could use the result of `str` to count character `char` in the new string. The count would simply be k+1 if the new character was equal to char and k otherwise.


## N queens problem

Let's say we already know the placement of `n` queens on an `nxn` board. We cannot use this information to find the answer for an `(n+1)x(n+1)` board. Look at the visualization below.




In this lesson, we will learn about some problem characteristics in dynamic programming.


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

Where to Use Dynamic Programming

Dynamic programming, the magic wand