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))

Перейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантів

Все було зрозуміло?

Секція 3. Розділ 2

Problem B. Minimum path

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))

Все було зрозуміло?

Секція 3. Розділ 2

Problem B. Minimum path

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))

Все було зрозуміло?

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))

Секція 3. Розділ 2