題目

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.

分析

給出一個非負(fù)整數(shù)的矩陣，找出從左上角到右下角數(shù)值之和最小的路徑。
也是使用動態(tài)規(guī)劃的思想，看從→和↓兩個方向到達(dá)的路徑哪條上的數(shù)值之和更小。
最后輸出值即可。類似的：http://www.itdecent.cn/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];
}