Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Overlapping Subproblems Property: Memoization | 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

bookOverlapping 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?

  1. Follow comments in the code.
  2. Test your program: call the function fib() for n = 12.
  3. Output the solved list like pairs of i, num to see the sub-solutions.

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 2
toggle bottom row

bookOverlapping 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?

  1. Follow comments in the code.
  2. Test your program: call the function fib() for n = 12.
  3. Output the solved list like pairs of i, num to see the sub-solutions.

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 2
toggle bottom row

bookOverlapping 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?

  1. Follow comments in the code.
  2. Test your program: call the function fib() for n = 12.
  3. Output the solved list like pairs of i, num to see the sub-solutions.

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 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?

  1. Follow comments in the code.
  2. Test your program: call the function fib() for n = 12.
  3. Output the solved list like pairs of i, num to see the sub-solutions.

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