Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Lernen Problem B. Minimum path | Solutions
Dynamic Programming

bookProblem 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].

123456789101112131415161718
def 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))
copy

War alles klar?

Wie können wir es verbessern?

Danke für Ihr Feedback!

Abschnitt 3. Kapitel 2
single

single

Fragen Sie AI

expand

Fragen Sie AI

ChatGPT

Fragen Sie alles oder probieren Sie eine der vorgeschlagenen Fragen, um unser Gespräch zu beginnen

Suggested prompts:

Zusammenfassen Sie dieses Kapitel

Code in file erklären

Erklären, warum file die Aufgabe nicht löst

close

Awesome!

Completion rate improved to 8.33

bookProblem B. Minimum path

Swipe um das Menü anzuzeigen

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].

123456789101112131415161718
def 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))
copy

Switch to desktopWechseln Sie zum Desktop, um in der realen Welt zu übenFahren Sie dort fort, wo Sie sind, indem Sie eine der folgenden Optionen verwenden
War alles klar?

Wie können wir es verbessern?

Danke für Ihr Feedback!

close

Awesome!

Completion rate improved to 8.33
Abschnitt 3. Kapitel 2
single

single

some-alt