题目

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

分析

给出一个非负整数的矩阵，找出从左上角到右下角数值之和最小的路径。
也是使用动态规划的思想，看从→和↓两个方向到达的路径哪条上的数值之和更小。
最后输出值即可。类似的：http://www.jianshu.com/p/717ccf2d69ee

int minPathSum(int** grid, int gridRowSize, int gridColSize) {
    int * ans=(int *)malloc(sizeof(int)*gridColSize);
    ans[0]=grid[0][0];
    for(int i=1;i<gridColSize;i++)
    {
        ans[i]=grid[0][i]+ans[i-1];
    }
    for(int i=1;i<gridRowSize;i++)
    {
        ans[0]=ans[0]+grid[i][0];
        for(int j=1;j<gridColSize;j++)
        {
            if(ans[j]<ans[j-1])
                ans[j]=ans[j]+grid[i][j];
            else
                ans[j]=ans[j-1]+grid[i][j];
        }
    }
    return ans[gridColSize-1];
}