« Back
in Leetcode Java Array Dynamic Programming read.

Leetcode 62 Unique Paths.

Problem 62 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?

robot Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

I think most people would think this as a backtracking problem.

The code can be really simple, too.

public class Solution {
    public int uniquePaths(int m, int n) {
        if(m==1 || n==1){
            return 1;
        }
        return uniquePaths(m-1,n)+uniquePaths(m,n-1);
    }
}

But, it will show Time Limit Exceeded.

So DP should be a good way to solve this.

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

comments powered by Disqus