leetcode 64. Minimum Path Sum (二维dp)

Posted by 111qqz on Monday, April 10, 2017

TOC

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.

数字三角形。。。。从坐上到右下问最短路径。。每次只能向下或者向右。。。

wa了一次。。。是因为边界值赋值成了0.。。求最短路径显然因为赋值成inf才对orz..果然傻了。。

简单的dp我们简单的A.

顺便吐槽一下。。(100,100)的答案会溢出int…然而答案就是负的。。。就没人check一下吗,,,

/* ***********************************************
Author :111qqz
Created Time :2017年04月10日 星期一 10时11分26秒
File Name :64.cpp
************************************************ */
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
    int n = grid.size();
    int m = grid[0].size();
    vector<vector<int> > dp(n+1,vector<int>(m+1,0x3f3f3f3f)); //求最小路径,初始化为最大值。

    dp[n-1][m-1] = grid[n-1][m-1];
    for ( int i = n-1 ;  i >= 0 ; i--)
    {
        for ( int j = m-1 ; j >= 0 ; j--)
        {
        if (i==n-1&&j==m-1) continue;
        dp[i][j] = min(dp[i+1][j],dp[i][j+1]) + grid[i][j];
        }
    }

    for ( int i = 0 ; i < n ; i++)
    {
        for ( int j = 0 ; j < m ; j++)
        printf("%d ",dp[i][j]);
        printf("\n");
    }
    int res = dp[0][0];
    cout<<"res:"<<res<<endl;
    return res;
    }
};

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付