Problem B. Minimum path
Let's traverse mat and update values in it: now mat[i][j] contains the path cost to cell [i, j]. How to reach that? You can get to the mat[i][j] from either mat[i-1][j] or mat[i][j-1] cell, that also contain the path cost to themselves. Thus, mat[i][j] can be updated as:
mat[i][j] += min(mat[i-1][j], mat[i][j-1]),
since you choose the minumum cost path between these two.
Note that some cells can be reached only from left or right, for example, mat[0][j] (only from mat[0][j-1]).
So, the goal is to traverse mat and update its values; after that, return path cost at mat[-1][-1].
123456789101112131415161718def minPath(mat): m, n = len(mat), len(mat[0]) for i in range(1, m): mat[i][0] += mat[i-1][0] for j in range(1, n): mat[0][j] += mat[0][j-1] for i in range(1, m): for j in range(1, n): mat[i][j] += min(mat[i-1][j], mat[i][j-1]) return mat[-1][-1] mat = [[10,1,23,4,5,1], [2,13,20,9,1,5], [14,3,3,6,12,7]] print(minPath(mat))
Дякуємо за ваш відгук!
single
Запитати АІ
Запитати АІ
Запитайте про що завгодно або спробуйте одне із запропонованих запитань, щоб почати наш чат
Сумаризуйте цей розділ
Пояснити код у file
Пояснити, чому file не вирішує завдання
Awesome!
Completion rate improved to 8.33Problem B. Minimum path
Свайпніть щоб показати меню
Let's traverse mat and update values in it: now mat[i][j] contains the path cost to cell [i, j]. How to reach that? You can get to the mat[i][j] from either mat[i-1][j] or mat[i][j-1] cell, that also contain the path cost to themselves. Thus, mat[i][j] can be updated as:
mat[i][j] += min(mat[i-1][j], mat[i][j-1]),
since you choose the minumum cost path between these two.
Note that some cells can be reached only from left or right, for example, mat[0][j] (only from mat[0][j-1]).
So, the goal is to traverse mat and update its values; after that, return path cost at mat[-1][-1].
123456789101112131415161718def minPath(mat): m, n = len(mat), len(mat[0]) for i in range(1, m): mat[i][0] += mat[i-1][0] for j in range(1, n): mat[0][j] += mat[0][j-1] for i in range(1, m): for j in range(1, n): mat[i][j] += min(mat[i-1][j], mat[i][j-1]) return mat[-1][-1] mat = [[10,1,23,4,5,1], [2,13,20,9,1,5], [14,3,3,6,12,7]] print(minPath(mat))
Перейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантівДякуємо за ваш відгук!
Awesome!
Completion rate improved to 8.33single
