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).
1234567891011121314def 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.
Swipe to start coding
Look at the following task code for the Fibonacci problem.
- Fix it to make the solution correct.
- Call the function for
n = 16and output the 16th Fibonacci number.
Solución
¡Gracias por tus comentarios!
single
Pregunte a AI
Pregunte a AI
Pregunte lo que quiera o pruebe una de las preguntas sugeridas para comenzar nuestra charla
Resumir este capítulo
Explicar el código en file
Explicar por qué file no resuelve la tarea
Awesome!
Completion rate improved to 8.33Overlapping Subproblems Property: Tabulation
Desliza para mostrar el menú
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).
1234567891011121314def 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.
Swipe to start coding
Look at the following task code for the Fibonacci problem.
- Fix it to make the solution correct.
- Call the function for
n = 16and output the 16th Fibonacci number.
Solución
Cambia al escritorio para practicar en el mundo realContinúe desde donde se encuentra utilizando una de las siguientes opciones¡Gracias por tus comentarios!
Awesome!
Completion rate improved to 8.33single
