Зміст курсу

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

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:


              123
            
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, or n==2, just return the respective value. These values are known, so no calculations are needed.

Завдання

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).

Завдання

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).

Перейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантів

Все було зрозуміло?

Секція 1. Розділ 4

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.

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:

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

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:


              123
            
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, or n==2, just return the respective value. These values are known, so no calculations are needed.

Завдання

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).

Завдання

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).

Все було зрозуміло?

Секція 1. Розділ 4

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.

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:

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

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:


              123
            
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, or n==2, just return the respective value. These values are known, so no calculations are needed.

Завдання

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).

Завдання

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).

Все було зрозуміло?

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.

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:

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

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:


              123
            
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, or n==2, just return the respective value. These values are known, so no calculations are needed.

Завдання

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).

Секція 1. Розділ 4