Minimum Path Sum in c#

General
1

The “Minimum Path Sum” problem involves finding the path from the top-left corner to the bottom-right corner of a grid (matrix) that minimizes the sum of the values along the path. You can only move either down or right at any point in time.

Approach

To solve this problem, we can use dynamic programming. The idea is to maintain a 2D array (or modify the input array) to store the minimum path sums up to each cell.

  1. Initialize the DP Array: Create a DP array where dp[i][j] represents the minimum path sum to reach cell (i, j).

  2. Base Cases:

    • The value at the starting cell dp[0][0] is simply the value of the grid at that cell.
    • For the first row and first column, the only way to reach those cells is from the left (for the first row) or from above (for the first column).

  3. Fill the DP Array:

    • For each cell (i, j), the minimum path sum is the value of that cell plus the minimum of the path sums from the top (dp[i-1][j]) and from the left (dp[i][j-1]).

  4. Return the Result: The value at the bottom-right corner of the DP array will give the minimum path sum.

Implementation in C#

Here’s a C# implementation of the above approach:

using System;

public class Program
{
    public static void Main()
    {
        int[][] grid = {
            new int[] { 1, 3, 1 },
            new int[] { 1, 5, 1 },
            new int[] { 4, 2, 1 }
        }; // Example grid
        
        int result = MinPathSum(grid);
        Console.WriteLine($"Minimum Path Sum: {result}");
    }

    public static int MinPathSum(int[][] grid)
    {
        if (grid == null || grid.Length == 0 || grid[0].Length == 0)
            return 0;

        int rows = grid.Length;
        int cols = grid[0].Length;

        // Create a DP array
        int[][] dp = new int[rows][];
        for (int i = 0; i < rows; i++)
        {
            dp[i] = new int[cols];
        }

        // Initialize the first cell
        dp[0][0] = grid[0][0];

        // Fill the first row
        for (int j = 1; j < cols; j++)
        {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }

        // Fill the first column
        for (int i = 1; i < rows; i++)
        {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }

        // Fill the rest of the DP array
        for (int i = 1; i < rows; i++)
        {
            for (int j = 1; j < cols; j++)
            {
                dp[i][j] = grid[i][j] + Math.Min(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        // Return the bottom-right corner value
        return dp[rows - 1][cols - 1];
    }
}

Explanation:

  1. Input Grid: The grid variable represents the matrix of integers.

  2. DP Array Initialization:

    • A 2D array dp is created to store the minimum path sums.
    • The first cell of the DP array is initialized to the value of the first cell in the grid.

  3. Filling the DP Array:

    • The first row and first column are filled with cumulative sums since there’s only one way to reach each cell in those cases.
    • For all other cells, we calculate the minimum path sum by taking the value of the current cell and adding the minimum of the sums from the top and left cells.

  4. Return Result: Finally, we return the value in the bottom-right corner of the DP array, which represents the minimum path sum from the top-left to the bottom-right corner of the grid.

Complexity:

  • Time Complexity: ( O(m \times n) ), where ( m ) is the number of rows and ( n ) is the number of columns in the grid, as we traverse each cell once.
  • Space Complexity: ( O(m \times n) ) for the DP array. However, it can be optimized to ( O(n) ) by using a single array for the current row and updating it as we go.

This dynamic programming approach provides an efficient way to solve the minimum path sum problem in a grid.