Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.What is DP | Intro to Dynamic Programming
Dynamic Programming
course content

Course Content

Dynamic Programming

Dynamic Programming

1. Intro to Dynamic Programming
What is DPOverlapping Subproblems Property: MemoizationOverlapping Subproblems Property: TabulationExample: Step by Step Solution
2. Problems
Problem A. Binomial CoefficientProblem B. Minimum pathProblem C. Minimum Path in TriangleProblem D. Coin Change
3. Solutions
Problem A. Binomial CoefficientProblem B. Minimum pathProblem C. Minimum Path in TriangleProblem D. Coin Change

bookWhat is DP

Dynamic programming is a programming paradigm for a massive class of problems. It solves the problem by partitioning it into smaller subproblems and solving it to avoid double computing the same results. Thus, the optimal solution of the main problem depends on the optimal solution of its subproblems.

The simplest (even classic) example is solving the Fibonacci Numbers problem - find the n-th Fibonacci number. As you know, each next Fibonacci number is a sum of the previous two Fibonacci numbers. So, if we have some function fib(n) that returns n-th Fibonacci numbers, we can implement it like this:


              
12

            
def fib(n):
  return fib(n-1) + fib(n-2)
copy

Thus, to solve the problem of the n-th Fibonacci number, you should solve the fib(n-1) and fib(n-2) subproblems first. But we can solve both of these subproblems in the same way.

You can note that this recursion has no bottom yet, so we have to add the stop condition:


              
1234

            
def fib(n):
  if n <= 1: # Bottom
    return n
  return fib(n-1) + fib(n-2)
copy

You'll find some info about the main DP properties in the next two chapters.

Task

  1. Following the example, implement the function fib(n).
  2. Make function calls to check how it works.

The function calls are already in the task code; do not change them. Edit the fib(n) function only.

Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Everything was clear?

How can we improve it?

Thanks for your feedback!

Section 1. Chapter 1
toggle bottom row

bookWhat is DP

Dynamic programming is a programming paradigm for a massive class of problems. It solves the problem by partitioning it into smaller subproblems and solving it to avoid double computing the same results. Thus, the optimal solution of the main problem depends on the optimal solution of its subproblems.

The simplest (even classic) example is solving the Fibonacci Numbers problem - find the n-th Fibonacci number. As you know, each next Fibonacci number is a sum of the previous two Fibonacci numbers. So, if we have some function fib(n) that returns n-th Fibonacci numbers, we can implement it like this:


              
12

            
def fib(n):
  return fib(n-1) + fib(n-2)
copy

Thus, to solve the problem of the n-th Fibonacci number, you should solve the fib(n-1) and fib(n-2) subproblems first. But we can solve both of these subproblems in the same way.

You can note that this recursion has no bottom yet, so we have to add the stop condition:


              
1234

            
def fib(n):
  if n <= 1: # Bottom
    return n
  return fib(n-1) + fib(n-2)
copy

You'll find some info about the main DP properties in the next two chapters.

Task

  1. Following the example, implement the function fib(n).
  2. Make function calls to check how it works.

The function calls are already in the task code; do not change them. Edit the fib(n) function only.

Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Everything was clear?

How can we improve it?

Thanks for your feedback!

Section 1. Chapter 1
toggle bottom row

bookWhat is DP

Dynamic programming is a programming paradigm for a massive class of problems. It solves the problem by partitioning it into smaller subproblems and solving it to avoid double computing the same results. Thus, the optimal solution of the main problem depends on the optimal solution of its subproblems.

The simplest (even classic) example is solving the Fibonacci Numbers problem - find the n-th Fibonacci number. As you know, each next Fibonacci number is a sum of the previous two Fibonacci numbers. So, if we have some function fib(n) that returns n-th Fibonacci numbers, we can implement it like this:


              
12

            
def fib(n):
  return fib(n-1) + fib(n-2)
copy

Thus, to solve the problem of the n-th Fibonacci number, you should solve the fib(n-1) and fib(n-2) subproblems first. But we can solve both of these subproblems in the same way.

You can note that this recursion has no bottom yet, so we have to add the stop condition:


              
1234

            
def fib(n):
  if n <= 1: # Bottom
    return n
  return fib(n-1) + fib(n-2)
copy

You'll find some info about the main DP properties in the next two chapters.

Task

  1. Following the example, implement the function fib(n).
  2. Make function calls to check how it works.

The function calls are already in the task code; do not change them. Edit the fib(n) function only.

Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Everything was clear?

How can we improve it?

Thanks for your feedback!

Dynamic programming is a programming paradigm for a massive class of problems. It solves the problem by partitioning it into smaller subproblems and solving it to avoid double computing the same results. Thus, the optimal solution of the main problem depends on the optimal solution of its subproblems.

The simplest (even classic) example is solving the Fibonacci Numbers problem - find the n-th Fibonacci number. As you know, each next Fibonacci number is a sum of the previous two Fibonacci numbers. So, if we have some function fib(n) that returns n-th Fibonacci numbers, we can implement it like this:


              
12

            
def fib(n):
  return fib(n-1) + fib(n-2)
copy

Thus, to solve the problem of the n-th Fibonacci number, you should solve the fib(n-1) and fib(n-2) subproblems first. But we can solve both of these subproblems in the same way.

You can note that this recursion has no bottom yet, so we have to add the stop condition:


              
1234

            
def fib(n):
  if n <= 1: # Bottom
    return n
  return fib(n-1) + fib(n-2)
copy

You'll find some info about the main DP properties in the next two chapters.

Task

  1. Following the example, implement the function fib(n).
  2. Make function calls to check how it works.

The function calls are already in the task code; do not change them. Edit the fib(n) function only.

Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Section 1. Chapter 1
Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
some-alt