Minimum Path Sum, Unique Paths, Unique Paths II

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.

Solution

• 2D DP problem, min of up and left cells are the unique path for current cell

---

Unique Paths

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?

Solution

• • 2D DP problem, sum of up and left cells are the unique path for current cell

public static int uniquePaths(int m, int n) {
     int[][] dp=new int[m][n];
     for(int i=0;i<m;i++){
         for(int j=0;j<n;j++){
             if(i==0 || j==0){
                 dp[i][j]=1;
             }
             else{
                 dp[i][j]=dp[i-1][j] +dp[i][j-1]; 
             }
             }
         }
         return dp[m-1][n-1];
     }

---

Unique Paths II

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.

Solution

• If up or left cell is 1, then set it to 0
• If current cell is 1, set it to 0

public static int uniquePathsWithObstacles(int[][] a)
	{
		int m=a.length; int n=a[0].length;
		int[][] dp=new int[m][n];
		int i=0;
		while(i<m){
			if(a[i][0]==1) break;
			else {dp[i][0]=1;i++;}
		}
		int j=0;
		while(j<n){
			if(a[0][j]==1) break;
			else {dp[0][j]=1;j++;}
		}

		for(i=1;i<m;i++){
			for(j=1;j<n;j++){
			        if(a[i][j]==1) dp[i][j]=0;//别忘了这个case
					else dp[i][j]= (a[i-1][j]==1 ? 0 : dp[i-1][j]) + (a[i][j-1]==1 ? 0 : dp[i][j-1]); //加括号...
			}
		}
		return dp[m-1][n-1];
	}