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))
Grazie per i tuoi commenti!
single
Chieda ad AI
Chieda ad AI
Chieda pure quello che desidera o provi una delle domande suggerite per iniziare la nostra conversazione
Riassuma questo capitolo
Explain code
Explain why doesn't solve task
Awesome!
Completion rate improved to 8.33Problem B. Minimum path
Scorri per mostrare il 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))
Cambia al desktop per esercitarti nel mondo realeContinua da dove ti trovi utilizzando una delle opzioni seguentiGrazie per i tuoi commenti!
Awesome!
Completion rate improved to 8.33single
