leetcode 64 | 最小路径和（动态规划）

输入:[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]

输出: 7

解释: 因为路径 1→3→1→1→1 的总和最小。

static inline int min(int a, int b)
{
    return a < b ? a : b;
}

int minPathSum(int** grid, int gridRowSize, int gridColSize)
{
    int i, j;
    //分配空间，行指针
    int **dp = malloc(gridRowSize * sizeof(int *));
    for (i = 0; i < gridRowSize; i++) {
        //对于每一行分配空间
        dp[i] = malloc(gridColSize * sizeof(int));
    }

    dp[0][0] = grid[0][0];
    //初始值为(0, 0)
    int sum = dp[0][0];

    //计算左边第一列的所有数字和
    for (i = 1; i < gridRowSize; i++) {
        sum += grid[i][0];
        dp[i][0] = sum;
    }

    sum = dp[0][0];
    //计算上面第一行的所有数字和
    for (i = 1; i < gridColSize; i++) {
        sum += grid[0][i];
        dp[0][i] = sum;
    }

    //遍历一遍整个grid，从第二行开始
    for (i = 1; i < gridRowSize; i++) {
        //从第2列开始
        for (j = 1; j < gridColSize; j++) {
            //对于与任意一点，判断是从左边推进还是从上边推进
            dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    //返回推进到的最后一个位置
    return dp[gridRowSize - 1][gridColSize - 1];
}