剑指 Offer II 099. 最小路径之和-双百代码

剑指 Offer II 099. 最小路径之和

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

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

示例 1：

输入：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

这题解题的重点在于知道，每个点由上面一个点或左面一个点得到
解题代码如下：

int minPathSum(int** grid, int gridSize, int* gridColSize){
    int i,j;
    int n=gridSize,m=gridColSize[0];
     // printf("nm %d %d || ",n,m);
      int k=fmin(m,n);
    for(i=0;i<k;i++){
        
        for(j=i;j<m;j++){
         //   printf("%d %d ",i,j);
            if(j==0&&i==0){
                continue;
            }
            if(i==0){
                    grid[i][j]=grid[i][j-1]+ grid[i][j];

              }
         else{
                if(grid[i][j-1]<grid[i-1][j]){
                     grid[i][j]=grid[i][j]+grid[i][j-1];

               }
                else{
                     grid[i][j]=grid[i][j]+grid[i-1][j];

               }
         }
    //      printf("%d %d  %d ",i,j,grid[i][j]);

        
        }
          for(j=i+1;j<n;j++){
               
            
                if(i==0){
                        grid[j][i]=grid[j-1][i]+ grid[j][i];

                }
            else{
                    if(grid[j][i-1]<grid[j-1][i]){
                        grid[j][i]=grid[j][i]+grid[j][i-1];

                }
                    else{
                        grid[j][i]=grid[j][i]+grid[j-1][i];

                }
            }
          //   printf("-%d %d  %d " ,j,i,grid[j][i]);

          }
    }
    return grid[n-1][m-1];


}