LeetCode //C – 64. Minimum Path Sum

本文介绍: 【代码】Lee tCod e //C – 64. Mini mum Pa th Sum。

64. Mini mum Path Sum

Gi ven a m x n grid filled wi th non-negati ve number s, find a path from top left t o bot t om right, whi ch minimizes the sum of all num bers along i ts pat h.

Note: You can only move eithe r down o r right at any point in time.

Ex ample 1:

在这里插入图片描述

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Ex planation: Because the pat h 1 → 3 → 1 → 1 → 1 minimizes the sum.

Ex ample 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

Con s train ts:

m == grid.length
n == gr id[i].length
1 <= m, n <= 200
0 <= gr id[i][j] <= 200

From: LeetCode
Lin k: 64. M inimum Path Sum

Solution:

Ideas：

This function assu mes that the memory fo r gr id has alread y been allocated and that gr idSize and gr idColSize are correctly set to reflect the dimensi ons of grid. The min function is a helper to find the mini mum of two num bers.

The function ca lc ulates the mini mum pat h sum in a bottom-up manner, fill ing in the dp table from the top–left to the bottom-right. After ca lc ulating the mini mum path sum, it cleans up the allocated memory for dp and returns the result.

Code:

int minPathSum(int** grid, int gridSize, int* gridColSize) {
    // The gridSize is the number of rows, and gridColSize[0] is the number of columns.
    int i, j;
    
    // Allocate space for the dp matrix
    int **dp = (int **)malloc(gridSize * sizeof(int *));
    for(i = 0; i < gridSize; i++) {
        dp[i] = (int *)malloc(gridColSize[0] * sizeof(int));
    }
    
    // Initialize the top-left corner
    dp[0][0] = grid[0][0];
    
    // Fill the first row (only right moves are possible)
    for(j = 1; j < gridColSize[0]; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    
    // Fill the first column (only down moves are possible)
    for(i = 1; i < gridSize; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    
    // Fill the rest of the dp matrix
    for(i = 1; i < gridSize; i++) {
        for(j = 1; j < gridColSize[0]; j++) {
            dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    
    // The bottom-right corner has the result
    int result = dp[gridSize - 1][gridColSize[0] - 1];
    
    // Free the dp matrix
    for(i = 0; i < gridSize; i++) {
        free(dp[i]);
    }
    free(dp);
    
    return result;
}

// Helper function to find the minimum of two numbers
int min(int a, int b) {
    return (a < b) ? a : b;
}