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
Запитати АІ
Запитати АІ
Запитайте про що завгодно або спробуйте одне із запропонованих запитань, щоб почати наш чат
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
