leetcode 64. Minimum Path Sum (二维dp)
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一下吗，，，
1/* ***********************************************
2Author :111qqz
3Created Time :2017年04月10日 星期一 10时11分26秒
4File Name :64.cpp
5************************************************ */
6class Solution {
7public:
8 int minPathSum(vector<vector<int>>& grid) {
9 int n = grid.size();
10 int m = grid[0].size();
11 vector<vector<int> > dp(n+1,vector<int>(m+1,0x3f3f3f3f)); //求最小路径，初始化为最大值。
1 dp[n-1][m-1] = grid[n-1][m-1];
2 for ( int i = n-1 ; i >= 0 ; i--)
3 {
4 for ( int j = m-1 ; j >= 0 ; j--)
5 {
6 if (i==n-1&&j==m-1) continue;
7 dp[i][j] = min(dp[i+1][j],dp[i][j+1]) + grid[i][j];
8 }
9 }
1 for ( int i = 0 ; i < n ; i++)
2 {
3 for ( int j = 0 ; j < m ; j++)
4 printf("%d ",dp[i][j]);
5 printf("\n");
6 }
7 int res = dp[0][0];
8 cout<<"res:"<<res<<endl;
9 return res;
10 }
11};