Course Content
Dynamic Programming
Dynamic Programming
Overlapping Subproblems Property: Memoization
Dynamic Programming combines solutions computed for sub-problems and stores them in the memory. Dynamic Programming mainly uses solutions to the same sub-problems repeatedly, and that’s the point. It makes sense to find a solution for each problem only once and reuse it later.
For example, unlike DP problems, the Merge Sort Algorithm also solves the subproblems like we do in DP but does not use these solutions multiple times.
In our Fibonacci problem, we solve the same problems multiple times. Why? Remember the formula for fib(n) = fib(n-1) + fib(n-2)? But for fib(n-1) we'll calculate the fib(n-2) and fib(n-3), and then calculate fib(n-2) again. Since we have no solution for fib(n-2) in memory, we'll repeat the same calculations multiple times. Here's why storing solved sub-problems in some tables makes sense.
Memoization
The memoized program is similar to the previous recursive solution but with additional space for storing values; let’s call it solved. When you solve some subproblem, put the solution to solved, and reuse it next time. The Memoization principle stores values from top to down, so it is also known as the Top-Down approach in Dynamic Programming.
Task
The function fib(n, solved) fills the list solved with Fibonacci numbers starting from 0 and up to n. Can you add some logic to store the sub-solutions?
- Follow comments in the code.
- Test your program: call the function
fib()forn = 12. - Output the
solvedlist like pairs ofi, numto see the sub-solutions.
Task
The function fib(n, solved) fills the list solved with Fibonacci numbers starting from 0 and up to n. Can you add some logic to store the sub-solutions?
- Follow comments in the code.
- Test your program: call the function
fib()forn = 12. - Output the
solvedlist like pairs ofi, numto see the sub-solutions.
Switch to desktop for real-world practiceContinue from where you are using one of the options belowEverything was clear?
Overlapping Subproblems Property: Memoization
Dynamic Programming combines solutions computed for sub-problems and stores them in the memory. Dynamic Programming mainly uses solutions to the same sub-problems repeatedly, and that’s the point. It makes sense to find a solution for each problem only once and reuse it later.
For example, unlike DP problems, the Merge Sort Algorithm also solves the subproblems like we do in DP but does not use these solutions multiple times.
In our Fibonacci problem, we solve the same problems multiple times. Why? Remember the formula for fib(n) = fib(n-1) + fib(n-2)? But for fib(n-1) we'll calculate the fib(n-2) and fib(n-3), and then calculate fib(n-2) again. Since we have no solution for fib(n-2) in memory, we'll repeat the same calculations multiple times. Here's why storing solved sub-problems in some tables makes sense.
Memoization
The memoized program is similar to the previous recursive solution but with additional space for storing values; let’s call it solved. When you solve some subproblem, put the solution to solved, and reuse it next time. The Memoization principle stores values from top to down, so it is also known as the Top-Down approach in Dynamic Programming.
Task
The function fib(n, solved) fills the list solved with Fibonacci numbers starting from 0 and up to n. Can you add some logic to store the sub-solutions?
- Follow comments in the code.
- Test your program: call the function
fib()forn = 12. - Output the
solvedlist like pairs ofi, numto see the sub-solutions.
Task
The function fib(n, solved) fills the list solved with Fibonacci numbers starting from 0 and up to n. Can you add some logic to store the sub-solutions?
- Follow comments in the code.
- Test your program: call the function
fib()forn = 12. - Output the
solvedlist like pairs ofi, numto see the sub-solutions.
Switch to desktop for real-world practiceContinue from where you are using one of the options belowEverything was clear?
Overlapping Subproblems Property: Memoization
Dynamic Programming combines solutions computed for sub-problems and stores them in the memory. Dynamic Programming mainly uses solutions to the same sub-problems repeatedly, and that’s the point. It makes sense to find a solution for each problem only once and reuse it later.
For example, unlike DP problems, the Merge Sort Algorithm also solves the subproblems like we do in DP but does not use these solutions multiple times.
In our Fibonacci problem, we solve the same problems multiple times. Why? Remember the formula for fib(n) = fib(n-1) + fib(n-2)? But for fib(n-1) we'll calculate the fib(n-2) and fib(n-3), and then calculate fib(n-2) again. Since we have no solution for fib(n-2) in memory, we'll repeat the same calculations multiple times. Here's why storing solved sub-problems in some tables makes sense.
Memoization
The memoized program is similar to the previous recursive solution but with additional space for storing values; let’s call it solved. When you solve some subproblem, put the solution to solved, and reuse it next time. The Memoization principle stores values from top to down, so it is also known as the Top-Down approach in Dynamic Programming.
Task
The function fib(n, solved) fills the list solved with Fibonacci numbers starting from 0 and up to n. Can you add some logic to store the sub-solutions?
- Follow comments in the code.
- Test your program: call the function
fib()forn = 12. - Output the
solvedlist like pairs ofi, numto see the sub-solutions.
Task
The function fib(n, solved) fills the list solved with Fibonacci numbers starting from 0 and up to n. Can you add some logic to store the sub-solutions?
- Follow comments in the code.
- Test your program: call the function
fib()forn = 12. - Output the
solvedlist like pairs ofi, numto see the sub-solutions.
Switch to desktop for real-world practiceContinue from where you are using one of the options belowEverything was clear?
Dynamic Programming combines solutions computed for sub-problems and stores them in the memory. Dynamic Programming mainly uses solutions to the same sub-problems repeatedly, and that’s the point. It makes sense to find a solution for each problem only once and reuse it later.
For example, unlike DP problems, the Merge Sort Algorithm also solves the subproblems like we do in DP but does not use these solutions multiple times.
In our Fibonacci problem, we solve the same problems multiple times. Why? Remember the formula for fib(n) = fib(n-1) + fib(n-2)? But for fib(n-1) we'll calculate the fib(n-2) and fib(n-3), and then calculate fib(n-2) again. Since we have no solution for fib(n-2) in memory, we'll repeat the same calculations multiple times. Here's why storing solved sub-problems in some tables makes sense.
Memoization
The memoized program is similar to the previous recursive solution but with additional space for storing values; let’s call it solved. When you solve some subproblem, put the solution to solved, and reuse it next time. The Memoization principle stores values from top to down, so it is also known as the Top-Down approach in Dynamic Programming.
Task
The function fib(n, solved) fills the list solved with Fibonacci numbers starting from 0 and up to n. Can you add some logic to store the sub-solutions?
- Follow comments in the code.
- Test your program: call the function
fib()forn = 12. - Output the
solvedlist like pairs ofi, numto see the sub-solutions.
Switch to desktop for real-world practiceContinue from where you are using one of the options belowSwitch to desktop for real-world practiceContinue from where you are using one of the options below