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

Sveip for å vise menyen

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


              
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 desktopBytt til skrivebordet for virkelighetspraksisFortsett der du er med et av alternativene nedenfor
Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 3. Kapittel 2

Spør AI

expand
ChatGPT

Spør om hva du vil, eller prøv ett av de foreslåtte spørsmålene for å starte chatten vår

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


              
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 desktopBytt til skrivebordet for virkelighetspraksisFortsett der du er med et av alternativene nedenfor
Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 3. Kapittel 2
Switch to desktopBytt til skrivebordet for virkelighetspraksisFortsett der du er med et av alternativene nedenfor
Vi beklager at noe gikk galt. Hva skjedde?
some-alt