Conteúdo do Curso
Dynamic Programming
Dynamic Programming
Problem C. Minimum Path in Triangle
The key to the solution is forming all possible minimum-cost paths from top to bottom row. You can not be sure which one will have minimum cost, so let's traverse a triangle and update values in the cells:
triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j]: thats how you can reach cell[i, j]` with min costtriangle[i][0] += triangle[i-1][0], triangle[i][i-1] += triangle[i-1][i-1]: extreme cases (number of columns in each row is equal to number of row).
After updating, choose the minimum path cost, which is in the last row.
def minPath(triangle): for i in range(1, len(triangle)): for j in range(i+1): small = 10000000 if j > 0: small = triangle[i-1][j-1] if j < i: small = min(small, triangle[i-1][j]) triangle[i][j] += small return min(triangle[-1]) triangle = [[90], [72, 6], [3, 61, 51], [90, 70, 23, 100], [79, 92, 72, 14, 1], [7, 97, 29, 100, 93, 93], [52, 95, 21, 36, 69, 69, 14], [33, 82, 20, 37, 79, 83, 21, 45]] print(minPath(triangle))
Mude para o desktop para praticar no mundo realContinue de onde você está usando uma das opções abaixoObrigado pelo seu feedback!
Problem C. Minimum Path in Triangle
The key to the solution is forming all possible minimum-cost paths from top to bottom row. You can not be sure which one will have minimum cost, so let's traverse a triangle and update values in the cells:
triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j]: thats how you can reach cell[i, j]` with min costtriangle[i][0] += triangle[i-1][0], triangle[i][i-1] += triangle[i-1][i-1]: extreme cases (number of columns in each row is equal to number of row).
After updating, choose the minimum path cost, which is in the last row.
def minPath(triangle): for i in range(1, len(triangle)): for j in range(i+1): small = 10000000 if j > 0: small = triangle[i-1][j-1] if j < i: small = min(small, triangle[i-1][j]) triangle[i][j] += small return min(triangle[-1]) triangle = [[90], [72, 6], [3, 61, 51], [90, 70, 23, 100], [79, 92, 72, 14, 1], [7, 97, 29, 100, 93, 93], [52, 95, 21, 36, 69, 69, 14], [33, 82, 20, 37, 79, 83, 21, 45]] print(minPath(triangle))
Mude para o desktop para praticar no mundo realContinue de onde você está usando uma das opções abaixoObrigado pelo seu feedback!
Problem C. Minimum Path in Triangle
The key to the solution is forming all possible minimum-cost paths from top to bottom row. You can not be sure which one will have minimum cost, so let's traverse a triangle and update values in the cells:
triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j]: thats how you can reach cell[i, j]` with min costtriangle[i][0] += triangle[i-1][0], triangle[i][i-1] += triangle[i-1][i-1]: extreme cases (number of columns in each row is equal to number of row).
After updating, choose the minimum path cost, which is in the last row.
def minPath(triangle): for i in range(1, len(triangle)): for j in range(i+1): small = 10000000 if j > 0: small = triangle[i-1][j-1] if j < i: small = min(small, triangle[i-1][j]) triangle[i][j] += small return min(triangle[-1]) triangle = [[90], [72, 6], [3, 61, 51], [90, 70, 23, 100], [79, 92, 72, 14, 1], [7, 97, 29, 100, 93, 93], [52, 95, 21, 36, 69, 69, 14], [33, 82, 20, 37, 79, 83, 21, 45]] print(minPath(triangle))
Mude para o desktop para praticar no mundo realContinue de onde você está usando uma das opções abaixoObrigado pelo seu feedback!
The key to the solution is forming all possible minimum-cost paths from top to bottom row. You can not be sure which one will have minimum cost, so let's traverse a triangle and update values in the cells:
triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j]: thats how you can reach cell[i, j]` with min costtriangle[i][0] += triangle[i-1][0], triangle[i][i-1] += triangle[i-1][i-1]: extreme cases (number of columns in each row is equal to number of row).
After updating, choose the minimum path cost, which is in the last row.
def minPath(triangle): for i in range(1, len(triangle)): for j in range(i+1): small = 10000000 if j > 0: small = triangle[i-1][j-1] if j < i: small = min(small, triangle[i-1][j]) triangle[i][j] += small return min(triangle[-1]) triangle = [[90], [72, 6], [3, 61, 51], [90, 70, 23, 100], [79, 92, 72, 14, 1], [7, 97, 29, 100, 93, 93], [52, 95, 21, 36, 69, 69, 14], [33, 82, 20, 37, 79, 83, 21, 45]] print(minPath(triangle))
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