Conteúdo do Curso
Dynamic Programming
Dynamic Programming
Problem B. Minimum path
The tasks in this section contain test function calls. Please do not change this code; otherwise, the assignment may not be accepted.
Given a two-dimensional array mat with values in it. Each value means the price we should pay for entering it. There is frog sitting in the top-left cell who wants to move to top-right. The frog can move to the nearest cell either right or down per one move. When it enters a cell, frog has to pay mat[i][j] for visiting it. Your goal is to find a path with minimal price. Return the cost of such a path.
Example 1
The orange path is minimum and costs 25.
Example 2
Input :
[[1, 3, 4],
[2, 1, 5],
[4, 6, 7]]
Output: 16
The path looks like:
Example 3
Input:
[[1, 2, 4],
[8, 5, 1]]
Output: 8
The Optimal Substructure here is to find the minimum path for each cell based on previous ones:
mat[i][j] = mat[i][j] + min(mat[i-1][j], mat[i][j-1])
This way, the minimum path to the mat[i][j] cell includes the price of this cell and the minimum price to one of the available cells (top or left).
Tarefa
Create an algorithm to find the shortest path for the frog.
- Use data structure
mat[n][n]as DS for storing the cost to the cellmat[i][j]. - Consider that you can visit current cell
mat[i][j]only from left or top cell (if it possible). - The answer is the value of
mat[-1][-1].
Tarefa
Create an algorithm to find the shortest path for the frog.
- Use data structure
mat[n][n]as DS for storing the cost to the cellmat[i][j]. - Consider that you can visit current cell
mat[i][j]only from left or top cell (if it possible). - The answer is the value of
mat[-1][-1].
Mude para o desktop para praticar no mundo realContinue de onde você está usando uma das opções abaixoTudo estava claro?
Problem B. Minimum path
The tasks in this section contain test function calls. Please do not change this code; otherwise, the assignment may not be accepted.
Given a two-dimensional array mat with values in it. Each value means the price we should pay for entering it. There is frog sitting in the top-left cell who wants to move to top-right. The frog can move to the nearest cell either right or down per one move. When it enters a cell, frog has to pay mat[i][j] for visiting it. Your goal is to find a path with minimal price. Return the cost of such a path.
Example 1
The orange path is minimum and costs 25.
Example 2
Input :
[[1, 3, 4],
[2, 1, 5],
[4, 6, 7]]
Output: 16
The path looks like:
Example 3
Input:
[[1, 2, 4],
[8, 5, 1]]
Output: 8
The Optimal Substructure here is to find the minimum path for each cell based on previous ones:
mat[i][j] = mat[i][j] + min(mat[i-1][j], mat[i][j-1])
This way, the minimum path to the mat[i][j] cell includes the price of this cell and the minimum price to one of the available cells (top or left).
Tarefa
Create an algorithm to find the shortest path for the frog.
- Use data structure
mat[n][n]as DS for storing the cost to the cellmat[i][j]. - Consider that you can visit current cell
mat[i][j]only from left or top cell (if it possible). - The answer is the value of
mat[-1][-1].
Tarefa
Create an algorithm to find the shortest path for the frog.
- Use data structure
mat[n][n]as DS for storing the cost to the cellmat[i][j]. - Consider that you can visit current cell
mat[i][j]only from left or top cell (if it possible). - The answer is the value of
mat[-1][-1].
Mude para o desktop para praticar no mundo realContinue de onde você está usando uma das opções abaixoTudo estava claro?
Problem B. Minimum path
The tasks in this section contain test function calls. Please do not change this code; otherwise, the assignment may not be accepted.
Given a two-dimensional array mat with values in it. Each value means the price we should pay for entering it. There is frog sitting in the top-left cell who wants to move to top-right. The frog can move to the nearest cell either right or down per one move. When it enters a cell, frog has to pay mat[i][j] for visiting it. Your goal is to find a path with minimal price. Return the cost of such a path.
Example 1
The orange path is minimum and costs 25.
Example 2
Input :
[[1, 3, 4],
[2, 1, 5],
[4, 6, 7]]
Output: 16
The path looks like:
Example 3
Input:
[[1, 2, 4],
[8, 5, 1]]
Output: 8
The Optimal Substructure here is to find the minimum path for each cell based on previous ones:
mat[i][j] = mat[i][j] + min(mat[i-1][j], mat[i][j-1])
This way, the minimum path to the mat[i][j] cell includes the price of this cell and the minimum price to one of the available cells (top or left).
Tarefa
Create an algorithm to find the shortest path for the frog.
- Use data structure
mat[n][n]as DS for storing the cost to the cellmat[i][j]. - Consider that you can visit current cell
mat[i][j]only from left or top cell (if it possible). - The answer is the value of
mat[-1][-1].
Tarefa
Create an algorithm to find the shortest path for the frog.
- Use data structure
mat[n][n]as DS for storing the cost to the cellmat[i][j]. - Consider that you can visit current cell
mat[i][j]only from left or top cell (if it possible). - The answer is the value of
mat[-1][-1].
Mude para o desktop para praticar no mundo realContinue de onde você está usando uma das opções abaixoTudo estava claro?
The tasks in this section contain test function calls. Please do not change this code; otherwise, the assignment may not be accepted.
Given a two-dimensional array mat with values in it. Each value means the price we should pay for entering it. There is frog sitting in the top-left cell who wants to move to top-right. The frog can move to the nearest cell either right or down per one move. When it enters a cell, frog has to pay mat[i][j] for visiting it. Your goal is to find a path with minimal price. Return the cost of such a path.
Example 1
The orange path is minimum and costs 25.
Example 2
Input :
[[1, 3, 4],
[2, 1, 5],
[4, 6, 7]]
Output: 16
The path looks like:
Example 3
Input:
[[1, 2, 4],
[8, 5, 1]]
Output: 8
The Optimal Substructure here is to find the minimum path for each cell based on previous ones:
mat[i][j] = mat[i][j] + min(mat[i-1][j], mat[i][j-1])
This way, the minimum path to the mat[i][j] cell includes the price of this cell and the minimum price to one of the available cells (top or left).
Tarefa
Create an algorithm to find the shortest path for the frog.
- Use data structure
mat[n][n]as DS for storing the cost to the cellmat[i][j]. - Consider that you can visit current cell
mat[i][j]only from left or top cell (if it possible). - The answer is the value of
mat[-1][-1].
Mude para o desktop para praticar no mundo realContinue de onde você está usando uma das opções abaixoMude para o desktop para praticar no mundo realContinue de onde você está usando uma das opções abaixo