LEETCODE，【leetcode】Minimum Path Sum

2023-10-15 阅读 26 评论 0

摘要：Minimum Path Sum 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. 動態規劃即可，

Minimum Path Sum

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.

動態規劃即可，與Unique Path類似

 1 class Solution {
 2 public:
 3     int minPathSum(vector<vector<int> > &grid) {
 4        
 5         int m=grid.size();
 6         int n=grid[0].size();
 7        
 8        /* int **dp=new int *[m];
 9         for(int i=0;i<m;i++)
10         {
11             dp[i]=new int[n];
12         }
13         */
14        
15         vector<vector<int>> dp(m,vector<int>(n));
16        
17         dp[0][0]=grid[0][0];
18        
19         for(int i=1;i<m;i++)
20         {
21             dp[i][0]=dp[i-1][0]+grid[i][0];
22         }
23        
24         for(int j=1;j<n;j++)
25         {
26             dp[0][j]=dp[0][j-1]+grid[0][j];
27         }
28        
29         for(int i=1;i<m;i++)
30         {
31             for(int j=1;j<n;j++)
32             {
33                 dp[i][j]=grid[i][j]+min(dp[i-1][j],dp[i][j-1]);
34             }
35         }
36        
37         return dp[m-1][n-1];
38        
39     }
40 };