Note: This article is available in Chinese only. 本文暂无英文版本。
View original
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)); //求最小路径，初始化为最大值。
12
13 dp[n-1][m-1] = grid[n-1][m-1];
14 for ( int i = n-1 ; i >= 0 ; i--)
15 {
16 for ( int j = m-1 ; j >= 0 ; j--)
17 {
18 if (i==n-1&&j==m-1) continue;
19 dp[i][j] = min(dp[i+1][j],dp[i][j+1]) + grid[i][j];
20 }
21 }
22
23 for ( int i = 0 ; i < n ; i++)
24 {
25 for ( int j = 0 ; j < m ; j++)
26 printf("%d ",dp[i][j]);
27 printf("\n");
28 }
29 int res = dp[0][0];
30 cout<<"res:"<<res<<endl;
31 return res;
32 }
33};