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.
1234567891011121314151617181920def 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))
Дякуємо за ваш відгук!
single
Запитати АІ
Запитати АІ
Запитайте про що завгодно або спробуйте одне із запропонованих запитань, щоб почати наш чат
Сумаризуйте цей розділ
Пояснити код у file
Пояснити, чому file не вирішує завдання
Чудово!
Completion показник покращився до 8.33Problem 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.
1234567891011121314151617181920def 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))
Перейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантівДякуємо за ваш відгук!
single
