Unique Paths Java

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?

Solution:DP 

Ways to destination point is equal to ways to up neighbor of destination point and left neighbor of destination point 

then we can generalize 

ways[m][n]=ways[m-1][n] + ways[m][n-1]

	/*
	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?
	*/
	// 1D DP
	public class Solution {
	public int uniquePaths(int m, int n) {
	if (m<0||n<0){
	return 0;
	}
	if (m==0 || n==0 ){
	return 1;
	}
	int[] arr=new int[n];
	arr[0]=1;
	for (int i=0; i<m; i++){
	for (int j=1; j<n; j++){
	arr[j]=arr[j]+arr[j-1];
	}
	}
	return arr[n-1];
	}
	}
	// 2D DP
	public class Solution {
	public int uniquePaths(int m, int n) {
	if (m<0||n<0){
	return 0;
	}
	if (m==0 || n==0 ){
	return 1;
	}
	int[][] matrix=new int[m][n];
	for (int i=0; i<m; i++){
	matrix[i][0]=1;
	}
	for (int i=0; i<n; i++){
	matrix[0][i]=1;
	}
	for (int i=1; i<m; i++){
	for (int j=1; j<n; j++){
	matrix[i][j]=matrix[i-1][j]+matrix[i][j-1];
	}
	}
	return matrix[m-1][n-1];
	}
	}

view raw UniquePath.java hosted with ❤ by GitHub