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))
Thanks for your feedback!
single
Ask AI
Ask AI
Ask anything or try one of the suggested questions to begin our chat
Summarize this chapter
Explain the code in file
Explain why file doesn't solve the task
Awesome!
Completion rate improved to 8.33Problem B. Minimum path
Swipe to show menu
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))
Switch to desktop for real-world practiceContinue from where you are using one of the options belowThanks for your feedback!
single
