Course Content
Dynamic Programming
Dynamic Programming
Example: Step by Step Solution
Optimal Substructure Property
There is another Dynamic Programming Property, and it means that a given problem has an optimal solution that we can calculate by using optimal solutions of its subproblems.
For example, if you want to get from city A to city B and then city C with the shortest distance, the shortest distance requires finding the shortest distances for ways A-B and B-C first (in case there are no other ways between A and C).
Let's solve the Rabbit on the Staircase problem to understand this approach.
Rabbit on the Staircase
Given a rabbit who wants to get to the top of the staircase – nth stair. Rabbit can jump only to the next stair, or missing one stair, or missing two, like in the image:
Your goal is to calculate the number of different ways to reach the nth stair. For example, there are 4 possible different ways to get to the 3rd stair. You can see them in the image above. These ways are unique. But the more stairs we have, the more opportunities to get to the last one.
Example 1
n = 3 -> res = 4
All 4 ways you can see on the image above.
Example 2
n=10 -> res = 274
It is difficult to imagine all the possible ways to reach the 10th step, so it is impossible to solve this problem manually. That's why we'll create an algorithm.
Algorithm
Consider that rabbit is on kth stair now. There are three ways to get there: from (k-1)th, (k-2)th, and (k-3)th stairs. The S(k) function returns the answer for the kth stair. Then, the number of different ways to reach the kth staircase is:
S(k) = S(k-1)+S(k-2)+S(k-3).
Similar to Fibonacci numbers, isn’t it? In this way, you can calculate the answer for stairs from 1 to n.
Optimal Substructure Property: you have to know the optimal solution for S(k-1), S(k-2), S(k-3) to solve the S(k).
Overlapping Subproblems Property: solve previous subproblems first and then store them in the memory.
Let’s use tabulation here: using dp list: dp[i] is a number of paths to reach ith staircase.
Define base cases:
dp[0] = 1 # You are already here, so there is 1 way dp[1] = 1 dp[2] = 2
Remember to process the corner cases: if
n==0,n==1, orn==2, just return the respective value. These values are known, so no calculations are needed.
Task
- Edit the task code to complete the algorithm for Rabbit on the Staircase problem.
- Submit the code with test calls (do not change this code).
Switch to desktop for real-world practiceContinue from where you are using one of the options belowThanks for your feedback!
Example: Step by Step Solution
Optimal Substructure Property
There is another Dynamic Programming Property, and it means that a given problem has an optimal solution that we can calculate by using optimal solutions of its subproblems.
For example, if you want to get from city A to city B and then city C with the shortest distance, the shortest distance requires finding the shortest distances for ways A-B and B-C first (in case there are no other ways between A and C).
Let's solve the Rabbit on the Staircase problem to understand this approach.
Rabbit on the Staircase
Given a rabbit who wants to get to the top of the staircase – nth stair. Rabbit can jump only to the next stair, or missing one stair, or missing two, like in the image:
Your goal is to calculate the number of different ways to reach the nth stair. For example, there are 4 possible different ways to get to the 3rd stair. You can see them in the image above. These ways are unique. But the more stairs we have, the more opportunities to get to the last one.
Example 1
n = 3 -> res = 4
All 4 ways you can see on the image above.
Example 2
n=10 -> res = 274
It is difficult to imagine all the possible ways to reach the 10th step, so it is impossible to solve this problem manually. That's why we'll create an algorithm.
Algorithm
Consider that rabbit is on kth stair now. There are three ways to get there: from (k-1)th, (k-2)th, and (k-3)th stairs. The S(k) function returns the answer for the kth stair. Then, the number of different ways to reach the kth staircase is:
S(k) = S(k-1)+S(k-2)+S(k-3).
Similar to Fibonacci numbers, isn’t it? In this way, you can calculate the answer for stairs from 1 to n.
Optimal Substructure Property: you have to know the optimal solution for S(k-1), S(k-2), S(k-3) to solve the S(k).
Overlapping Subproblems Property: solve previous subproblems first and then store them in the memory.
Let’s use tabulation here: using dp list: dp[i] is a number of paths to reach ith staircase.
Define base cases:
dp[0] = 1 # You are already here, so there is 1 way dp[1] = 1 dp[2] = 2
Remember to process the corner cases: if
n==0,n==1, orn==2, just return the respective value. These values are known, so no calculations are needed.
Task
- Edit the task code to complete the algorithm for Rabbit on the Staircase problem.
- Submit the code with test calls (do not change this code).
Switch to desktop for real-world practiceContinue from where you are using one of the options belowThanks for your feedback!
Example: Step by Step Solution
Optimal Substructure Property
There is another Dynamic Programming Property, and it means that a given problem has an optimal solution that we can calculate by using optimal solutions of its subproblems.
For example, if you want to get from city A to city B and then city C with the shortest distance, the shortest distance requires finding the shortest distances for ways A-B and B-C first (in case there are no other ways between A and C).
Let's solve the Rabbit on the Staircase problem to understand this approach.
Rabbit on the Staircase
Given a rabbit who wants to get to the top of the staircase – nth stair. Rabbit can jump only to the next stair, or missing one stair, or missing two, like in the image:
Your goal is to calculate the number of different ways to reach the nth stair. For example, there are 4 possible different ways to get to the 3rd stair. You can see them in the image above. These ways are unique. But the more stairs we have, the more opportunities to get to the last one.
Example 1
n = 3 -> res = 4
All 4 ways you can see on the image above.
Example 2
n=10 -> res = 274
It is difficult to imagine all the possible ways to reach the 10th step, so it is impossible to solve this problem manually. That's why we'll create an algorithm.
Algorithm
Consider that rabbit is on kth stair now. There are three ways to get there: from (k-1)th, (k-2)th, and (k-3)th stairs. The S(k) function returns the answer for the kth stair. Then, the number of different ways to reach the kth staircase is:
S(k) = S(k-1)+S(k-2)+S(k-3).
Similar to Fibonacci numbers, isn’t it? In this way, you can calculate the answer for stairs from 1 to n.
Optimal Substructure Property: you have to know the optimal solution for S(k-1), S(k-2), S(k-3) to solve the S(k).
Overlapping Subproblems Property: solve previous subproblems first and then store them in the memory.
Let’s use tabulation here: using dp list: dp[i] is a number of paths to reach ith staircase.
Define base cases:
dp[0] = 1 # You are already here, so there is 1 way dp[1] = 1 dp[2] = 2
Remember to process the corner cases: if
n==0,n==1, orn==2, just return the respective value. These values are known, so no calculations are needed.
Task
- Edit the task code to complete the algorithm for Rabbit on the Staircase problem.
- Submit the code with test calls (do not change this code).
Switch to desktop for real-world practiceContinue from where you are using one of the options belowThanks for your feedback!
Optimal Substructure Property
There is another Dynamic Programming Property, and it means that a given problem has an optimal solution that we can calculate by using optimal solutions of its subproblems.
For example, if you want to get from city A to city B and then city C with the shortest distance, the shortest distance requires finding the shortest distances for ways A-B and B-C first (in case there are no other ways between A and C).
Let's solve the Rabbit on the Staircase problem to understand this approach.
Rabbit on the Staircase
Given a rabbit who wants to get to the top of the staircase – nth stair. Rabbit can jump only to the next stair, or missing one stair, or missing two, like in the image:
Your goal is to calculate the number of different ways to reach the nth stair. For example, there are 4 possible different ways to get to the 3rd stair. You can see them in the image above. These ways are unique. But the more stairs we have, the more opportunities to get to the last one.
Example 1
n = 3 -> res = 4
All 4 ways you can see on the image above.
Example 2
n=10 -> res = 274
It is difficult to imagine all the possible ways to reach the 10th step, so it is impossible to solve this problem manually. That's why we'll create an algorithm.
Algorithm
Consider that rabbit is on kth stair now. There are three ways to get there: from (k-1)th, (k-2)th, and (k-3)th stairs. The S(k) function returns the answer for the kth stair. Then, the number of different ways to reach the kth staircase is:
S(k) = S(k-1)+S(k-2)+S(k-3).
Similar to Fibonacci numbers, isn’t it? In this way, you can calculate the answer for stairs from 1 to n.
Optimal Substructure Property: you have to know the optimal solution for S(k-1), S(k-2), S(k-3) to solve the S(k).
Overlapping Subproblems Property: solve previous subproblems first and then store them in the memory.
Let’s use tabulation here: using dp list: dp[i] is a number of paths to reach ith staircase.
Define base cases:
dp[0] = 1 # You are already here, so there is 1 way dp[1] = 1 dp[2] = 2
Remember to process the corner cases: if
n==0,n==1, orn==2, just return the respective value. These values are known, so no calculations are needed.
Task
- Edit the task code to complete the algorithm for Rabbit on the Staircase problem.
- Submit the code with test calls (do not change this code).
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