Minimum Path Sum

You can solve this problem by using Dynamic Programming. Here’s the step-by-step process:

1. Initialization: Create a 2D array dp with the same dimensions as the grid, where dp[i][j] will represent the minimum sum to reach the cell (i, j) from the top-left corner.

2. Base Case: The minimum sum to reach the top-left corner itself is the value at that cell, so dp[0][0] = grid[0][0].

3. Calculate the First Row and Column: Since you can only move right or down, the values in the first row and first column can be calculated easily by summing the previous value with the current grid value.

4. Iterate Through the Grid: Now, for the rest of the cells (i, j), you can only reach them from the left (i, j-1) or from above (i-1, j). So, take the minimum of these two paths and add the value at the current grid cell.

5. Return the Result: The value at dp[m-1][n-1] will give you the minimum path sum from the top-left to the bottom-right corner.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]

        # Base Case
        dp[0][0] = grid[0][0]

        # Calculate the first row
        for j in range(1, n):
            dp[0][j] = dp[0][j-1] + grid[0][j]

        # Calculate the first column
        for i in range(1, m):
            dp[i][0] = dp[i-1][0] + grid[i][0]

        # Iterate through the grid
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

        return dp[m-1][n-1]

This code will give you the minimum path sum, as required by the problem. The time complexity of this solution is ( O(m \cdot n) ), where ( m ) and ( n ) are the number of rows and columns in the grid, respectively. The space complexity is also ( O(m \cdot n) ), as we are using a 2D array to store our results.

minimize something : optimization problem

Greedy appraoch: Exmaple 1 : leads to wrong answer Bruteforce : Time complexity is not good What approach can be used to find the optimal solution?

Find one solution that is minimal sum.

DP Approach

[1, 3, 1] => [1, 4, 5]

We calculated the prefix sum.

1. Optimal substructure

2. Overlapping subproblems Identify the state? cost(r, c) = [() ()]

   cost(1, 1) = 1 cost(1, 2) = 1 + 3 = 4 cost(1, 3) = 4 + 1 = 5

cost(r, c) = grid[r][c] + min(cost(r, c-1), cost(r-1, c))

dp table with mxn

T:O(N^2) S:O(MxN)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# @param {Integer[][]} grid
# @return {Integer}

def min_path_sum(grid)
  rows = grid.size
  cols = grid[0].size

  dp = Array.new(rows) { Array.new(cols, 0)}
    
  dp[0][0] = grid[0][0]
  
  for i in (1...rows)
     dp[i][0] = dp[i-1][0] + grid[i][0] 
  end
  
  for i in (1...cols)
     dp[0][i] = dp[0][i - 1] + grid[0][i] 
  end

  for i in (1...rows)
     for j in (1...cols)
#       cost(r, c) = grid[r][c] + min(cost(r, c-1), cost(r-1, c))
        dp[i][j] = grid[i][j] + [dp[i-1][j], dp[i][j-1]].min 
     end
  end

  return dp[rows-1][cols-1]
end