[Leetcode] Unique Path

Problem

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?

Analysis

• 对于每一格，有两种到达它的方式，即从左边，或者从上边
• 所以 count[i][j] = count[i-1][j] + count[i][j-1]
• Time: O(n^2)
• Space: O(n^2)
• Space可以进行优化为O(n), 因为计算count每一行的值的时候只需要上一行的信息

Code

	public class Solution {
	public int uniquePaths(int m, int n) {
	//count[i][j] represents the number of ways to reach grid[i][j]
	int[][] count = new int[m][n];
	//for each grid, we can reach it by each from left-side or top-side
	for(int i=0; i<m; i++){
	for(int j=0; j<n; j++){
	if(i==0 || j==0) count[i][j] = 1;
	else count[i][j] = count[i-1][j] + count[i][j-1];
	}
	}
	return count[m-1][n-1];
	}
	}
	///////////////////////////////////
	// Optimize Space to O(n)
	public class Solution {
	public int uniquePaths(int m, int n) {
	//Optimize space to O(n)
	//We only need to keep track of # of ways to last line
	int[] count = new int[n];
	for(int i=0; i<m; i++){
	for(int j=0; j<n; j++){
	if(i==0 || j==0) count[j] = 1;
	//(# of ways to grid[i][j]) = (# of ways to grid[i-1][j]) + (# of ways to grid[i][j-1])
	else count[j] = count[j] + count[j-1];
	}
	}
	return count[n-1];
	}
	}

view raw unique-paths.java hosted with ❤ by GitHub