64. Minimum Path Sum

64. Minimum Path Sum My Submissions
Question
Total Accepted: 62294 
Total Submissions: 183284 
Difficulty: Medium
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.
Subscribe to see which companies asked this question
Hide Tags
 
Array Dynamic Programming
Show Similar Problems
分析:
明らかなダイナミックプランニングの問題です.
サブ問題の定義:原点(1,1)から目的点(m,n)までの最小路力とresult[m,n]のいずれかの点の路力とが2次元配列上の行からの最小路力または右列からの最小路力と現在位置の値と加算された結果、result[m,n]=min(result[m-1,n]+grid[m,n],result[m,n-1]+grid[m,n])で初期化問題に注意する

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int row=grid.size();// 
        int col=grid[0].size();
        vector< vector<int> >  result(row);     
        for(int i=0;i <row ;i++)     
            result[i].resize(col,0);//       row ，col  
        result[0][0]=grid[0][0];//       
        for(int i=1;i<col;i++)//      
            result[0][i]=result[0][i-1]+grid[0][i];
        for(int i=1;i<row;i++)//      
            result[i][0]=result[i-1][0]+grid[i][0];
        for(int i=1;i<row;i++)//      
            for(int j=1;j<col;j++)
                result[i][j]=min(result[i][j-1]+grid[i][j],result[i-1][j]+grid[i][j]);
        return result[row-1][col-1];
    }
};

連動の他の2つの問題:
62. Unique Paths   My Submissions
Question
Total Accepted: 75227 
Total Submissions: 214539 
Difficulty: Medium
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
Subscribe to see which companies asked this question
Hide Tags
 
Array Dynamic Programming
Show Similar Problems
分析:
定義サブ問題:原点(1,1)から目的点(m,n)までの最大走法数をdp[m,n]とするいずれの点も上から降りることと右から来ることの2つの可能性と明らかなdp[m,n]=dp[m-1,n]+dp[m,n-1]最も簡単な動的計画問題.......
時間複雑度O(M*N)、空間複雑度O(M*N)

class Solution {    
public:    
    int uniquePaths(int m, int n) {    
        vector< vector<int> >  result(m+1);     
        for(int i=0;i <=m ;i++)     
                result[i].resize(n+1);//       m+1 ，n+1      
        for(int i=1;i<=n;i++)    
            result[1][i]=1;    
        for(int i=1;i<=m;i++)    
            result[i][1]=1;    
        for(int i=2;i<=m;i++)    
            for(int j=2;j<=n;j++)    
                result[i][j]=result[i-1][j]+result[i][j-1];    
        return result[m][n];    
    }    
}; 

63. Unique Paths II   My Submissions
Question
Total Accepted: 55136 
Total Submissions: 191949 
Difficulty: Medium
Follow up for「Unique Paths」:前回の「唯一の道力」に続いて、グリッドに障害があり、到着できないことを考慮して、到着先のルート数を再計算してください
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as  1  and  0  respectively in the grid.
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is  2 .
Note: m and n will be at most 100.
Subscribe to see which companies asked this question
Hide Tags
 
Array Dynamic Programming
Hide Similar Problems
 
(M) Unique Paths
分析:
この問題は元の問題と比べて、何になりますか.1,この障害物の下と右はこれに由来する数を獲得していないということは、寄与が0 2であるということも理解できるし、障害のある場所にも到達できない(この1本の始まりは思わなかったが、どうもleetcodeの意味がはっきりしたくない)、つまりこの点の到達可能な道路力数は直接0である

<span style="font-size:12px;">class Solution {  
public:  
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {  
        int m=obstacleGrid.size();  
        int n=obstacleGrid[0].size();  
        vector< vector<int> >  result(m+1);     
        for(int i=0;i <=m ;i++)     
            result[i].resize(n+1);//       m+1 ，n+1      
        //        ，           
        result[1][1]= obstacleGrid[0][0]==1? 0:1;      
        for(int i=2;i<=n;i++)    
            result[1][i]=obstacleGrid[0][i-1]==1?0:result[1][i-1];//           
        for(int i=2;i<=m;i++)    
            result[i][1]=obstacleGrid[i-1][0]==1?0:result[i-1][1];    
              
        for(int i=2;i<=m;i++)    
            for(int j=2;j<=n;j++)    
                result[i][j]=obstacleGrid[i-1][j-1]==1?0:result[i-1][j]+result[i][j-1];  //            ，      
              
        return result[m][n];  
    }  
}; </span><span style="font-size: 14px;"> </span>

注:本博文はEbowTangオリジナルで、その後も本論文を更新する可能性があります.転載する場合は、必ずこの情報をコピーしてください!
原文住所:http://blog.csdn.net/ebowtang/article/details/50640213
原作者ブログ:http://blog.csdn.net/ebowtang