Contenido del Curso

Dynamic Programming

1. Intro to Dynamic Programming

What is DP Overlapping Subproblems Property: Memoization Overlapping Subproblems Property: Tabulation Example: Step by Step Solution

2. Problems

Problem A. Binomial Coefficient Problem B. Minimum path Problem C. Minimum Path in Triangle Problem D. Coin Change

3. Solutions

Problem A. Binomial Coefficient Problem B. Minimum path Problem C. Minimum Path in Triangle Problem D. Coin Change

Overlapping Subproblems Property: Tabulation

Tabulation

"First, solve all necessary subproblems, and then solve the main problem."

Such a principle is called the Bottom-Up approach. We start with trivial subproblems and move from the bottom to the answer. This principle also uses additional tables to store solutions.

Example

Let’s create an array dp to store the solutions. (dp can be a common name for data structure in a class of DP problems).


              1234567891011121314
            
def fib(n):
 
  # Array declaration
  dp = [0]*(n+1)
 
  # Base case assignment
  dp[0] = 0
  dp[1] = 1
 
  # Calculating and storing the values for trivial cases
  for i in range(2 , n+1):
    dp[i] = dp[i-1] + dp[i-2]
  return dp[n]

Since we know how to calculate the next element using the previous two elements, let's move from the pre-defined first two elements (base case) and figure out the solution for the 3rd sub-problem. After that, solve the 4th sub-problem using the 2nd and 3rd, and so on, until the last element.

Tarea

Look at the following task code for the Fibonacci problem.

Fix it to make the solution correct.
Call the function for n = 16 and output the 16th Fibonacci number.

Tarea

Look at the following task code for the Fibonacci problem.

Fix it to make the solution correct.
Call the function for n = 16 and output the 16th Fibonacci number.

Cambia al escritorio para practicar en el mundo realContinúe desde donde se encuentra utilizando una de las siguientes opciones

¿Todo estuvo claro?

Sección 1. Capítulo 3

Overlapping Subproblems Property: Tabulation

Tabulation

"First, solve all necessary subproblems, and then solve the main problem."

Such a principle is called the Bottom-Up approach. We start with trivial subproblems and move from the bottom to the answer. This principle also uses additional tables to store solutions.

Example

Let’s create an array dp to store the solutions. (dp can be a common name for data structure in a class of DP problems).


              1234567891011121314
            
def fib(n):
 
  # Array declaration
  dp = [0]*(n+1)
 
  # Base case assignment
  dp[0] = 0
  dp[1] = 1
 
  # Calculating and storing the values for trivial cases
  for i in range(2 , n+1):
    dp[i] = dp[i-1] + dp[i-2]
  return dp[n]

Tarea

Look at the following task code for the Fibonacci problem.

Fix it to make the solution correct.
Call the function for n = 16 and output the 16th Fibonacci number.

Tarea

Look at the following task code for the Fibonacci problem.

Fix it to make the solution correct.
Call the function for n = 16 and output the 16th Fibonacci number.

Cambia al escritorio para practicar en el mundo realContinúe desde donde se encuentra utilizando una de las siguientes opciones

¿Todo estuvo claro?

Sección 1. Capítulo 3

Overlapping Subproblems Property: Tabulation

Tabulation

"First, solve all necessary subproblems, and then solve the main problem."

Such a principle is called the Bottom-Up approach. We start with trivial subproblems and move from the bottom to the answer. This principle also uses additional tables to store solutions.

Example

Let’s create an array dp to store the solutions. (dp can be a common name for data structure in a class of DP problems).


              1234567891011121314
            
def fib(n):
 
  # Array declaration
  dp = [0]*(n+1)
 
  # Base case assignment
  dp[0] = 0
  dp[1] = 1
 
  # Calculating and storing the values for trivial cases
  for i in range(2 , n+1):
    dp[i] = dp[i-1] + dp[i-2]
  return dp[n]

Tarea

Look at the following task code for the Fibonacci problem.

Fix it to make the solution correct.
Call the function for n = 16 and output the 16th Fibonacci number.

Tarea

Look at the following task code for the Fibonacci problem.

Fix it to make the solution correct.
Call the function for n = 16 and output the 16th Fibonacci number.

Cambia al escritorio para practicar en el mundo realContinúe desde donde se encuentra utilizando una de las siguientes opciones

¿Todo estuvo claro?

Tabulation

"First, solve all necessary subproblems, and then solve the main problem."

Such a principle is called the Bottom-Up approach. We start with trivial subproblems and move from the bottom to the answer. This principle also uses additional tables to store solutions.

Example

Let’s create an array dp to store the solutions. (dp can be a common name for data structure in a class of DP problems).


              1234567891011121314
            
def fib(n):
 
  # Array declaration
  dp = [0]*(n+1)
 
  # Base case assignment
  dp[0] = 0
  dp[1] = 1
 
  # Calculating and storing the values for trivial cases
  for i in range(2 , n+1):
    dp[i] = dp[i-1] + dp[i-2]
  return dp[n]

Tarea

Look at the following task code for the Fibonacci problem.

Fix it to make the solution correct.
Call the function for n = 16 and output the 16th Fibonacci number.

Cambia al escritorio para practicar en el mundo realContinúe desde donde se encuentra utilizando una de las siguientes opciones

Sección 1. Capítulo 3

Cambia al escritorio para practicar en el mundo realContinúe desde donde se encuentra utilizando una de las siguientes opciones