Posted on 2014-01-19 02:57
Uriel 閱讀(149)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
LeetCode
給一個(gè)數(shù)字矩陣，求從左上角到右下角數(shù)字和最小的一條路徑，輸出數(shù)字和，(每次僅能往右或往下走)
1 class Solution {
2 public:
3 int dp[1010][1010];
4 int minPathSum(vector<vector<int> > &grid) {
5 if(grid.empty()) return 0;
6 for(int i = 0; i < grid.size(); ++i) {
7 for(int j = 0; j < grid[0].size(); ++j) {
8 if(!i && !j) dp[i][j] = grid[i][j];
9 else if(!i) dp[i][j] = dp[i][j - 1] + grid[i][j];
10 else if(!j) dp[i][j] = dp[i - 1][j] + grid[i][j];
11 else
12 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
13 }
14 }
15 return dp[grid.size() - 1][grid[0].size() - 1];
16 }
17 };