跳转至

64. 最小路径和

难度：中等

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：

Example

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 100

Reference

题解

设第\(i\)行第\(j\)列的元素\(a_{ij}\)到右下角路径上的数字和为\(f(i, j)\)，特别地，有\(f(m, n) = a_{mn}\)，则：

对于最后一行元素，只能向右移动，有：

\[ f(m, j) = \sum_{k=j} ^{n} a_{mk} \]

同理，对于最后一列元素，有：

\[ f(i, n) = \sum_{k = i} ^ {m} a_{kn} \]

设第\(i\)行到达右下角的最短路径和（即\(f(i, j), \forall j\)）以及第\(i - 1\)行最后一列到达右下角的最短路径和，即\(f(i - 1, n)\)已知。由于每一步只能向右或向下移动，\(f(i - 1, j)\)可以通过如下方程推导：

\[ f(i - 1, j - 1) = \min\{f(i - 1, j), f(i, j - 1)\} + a_{(i - 1)(j - 1)} \]

由此得到状态转移方程，即可使用动态规划自底向上求解。求解过程中只需要存储一行的最短路径和即可。

#define MIN(x, y) ((x) < (y) ? x : y)
int minPathSum(int** grid, int gridSize, int* gridColSize){
    if (gridSize == 0 || *gridColSize == 0)
        return 0;
    int *dp = (int *)memset(malloc(sizeof(int) * *gridColSize), 0, sizeof(int) * *gridColSize),
        i = 0, j = 0;
    for (i = 0; i < *gridColSize; i++)
        dp[i] = INT_MAX;
    dp[0] = 0;
    for (i = 0; i < gridSize; i++)
    {
        dp[0] += grid[i][0];
        for (j = 1; j < *gridColSize; j++)
            dp[j] = MIN(dp[j - 1], dp[j]) + grid[i][j];
    }
    return dp[*gridColSize - 1];
}

评论