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

Course Content

Dynamic Programming

Dynamic Programming

1. Intro to Dynamic Programming
What is DPOverlapping Subproblems Property: MemoizationOverlapping Subproblems Property: TabulationExample: Step by Step Solution
2. Problems
Problem A. Binomial CoefficientProblem B. Minimum pathProblem C. Minimum Path in TriangleProblem D. Coin Change
3. Solutions
Problem A. Binomial CoefficientProblem B. Minimum pathProblem C. Minimum Path in TriangleProblem D. Coin Change

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

Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Everything was clear?

How can we improve it?

Thanks for your feedback!

Section 3. Chapter 2
toggle bottom row

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

Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Everything was clear?

How can we improve it?

Thanks for your feedback!

Section 3. Chapter 2
toggle bottom row

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

Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Everything was clear?

How can we improve it?

Thanks for your feedback!

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 desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Section 3. Chapter 2
Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
some-alt