0064 最小路径和

算法思路

很容易想到，这是动态规划。由于存在相同子问题，我们走到点 gris[i][j] 的最短距离，仅与走到 grid[i-1][j] 或 grid[i][j-1] 的最短距离相关（i, j > 0）。

易得状态转移方程：

\[ \displaystyle minPath[i][j] = \left \{ \begin{array}{cc} \min (minPath[i-1][j],minPath[i][j-1])+grid[i][j] & \text{i, j > 0}\\ minPath[0][j-1]+grid[i][j] & \text{i = 0}\\ minPath[i-1][0]+grid[i][j] & \text{j = 0} \end{array} \right. \]

并且有 \(minPath[0][0]=grid[0][0]\)。

代码实现

minimum-path-sum.c

#define min(a, b) ((b) < (a) ? (b) : (a))

int minPathSum(int** grid, int gridSize, int* gridColSize) {
    int ret[gridSize][gridColSize[0]];
    memset(ret, 0, gridSize * gridColSize[0] * sizeof(int));
    ret[0][0] = grid[0][0];
    for (int i = 1; i < gridSize; i++) {
        ret[i][0] = ret[i - 1][0] + grid[i][0];
    }
    for (int i = 1; i < gridColSize[0]; i++) {
        ret[0][i] = ret[0][i - 1] + grid[0][i];
    }
    for (int i = 1; i < gridSize; i++) {
        for (int j = 1; j < gridColSize[0]; j++) {
            // int minPath = 1e8, more = grid[i][j];
            // minPath = min(minPath, ret[i - 1][j] + grid[i][j]);
            // for (int index = j - 1; index >= 0; index--) {
            //     minPath = min(minPath, ret[i][index] + more);
            //     more += grid[i][index];
            // }
            ret[i][j] = min(ret[i - 1][j], ret[i][j - 1]) + grid[i][j];
        }
    }
    return ret[gridSize - 1][gridColSize[0] - 1];
}