程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 64. Minimum Path Sum,64minimumpathsum

64. Minimum Path Sum,64minimumpathsum

編輯:C++入門知識

64. Minimum Path Sum,64minimumpathsum


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.

 

 1 class Solution {
 2 public:
 3     int minPathSum(vector<vector<int>>& grid) {
 4         if(grid.size() == 0 || grid[0].size() == 0){
 5             return 0;
 6         }
 7         
 8         int row = grid.size();
 9         int col = grid[0].size();
10         
11         int dp[row][col];
12         
13         dp[0][0] = grid[0][0];
14         
15         for(int i = 1; i < row; i++){
16             dp[i][0] = dp[i-1][0] + grid[i][0];
17         }
18         
19         for(int j = 1; j < col; j++){
20             dp[0][j] = dp[0][j-1] + grid[0][j];
21         }
22         
23         for(int i = 1; i < row; i++){
24             for(int j =1; j < col; j++){
25                 dp[i][j] = min(dp[i-1][j] , dp[i][j-1]) + grid[i][j];
26             }
27         }
28         return dp[row-1][col-1];
29     }
30 };

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved