Problem

A robot is located at the top-left corner of a m x n grid. It 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.

How many possible unique paths are there?

JavaScript Code

function uniquePaths(m, n) {
    if(m==0 || n==0) return 0;
    if(m==1 || n==1) return 1;
 
    var dp = [];
 
    for(var i=0; i<m; i++){
        var temp = [];
        for(var j=0; j<n; j++){
            temp.push(0);
        }
        dp.push(temp);
    }
    
    //left column
    for(var i=0; i<m; i++){
        dp[i][0] = 1;
    }
    
    
    //top row
    for(var j=0; j<n; j++){
        dp[0][j] = 1;
    }
    
    //fill up the dp table
    for(var i=1; i<m; i++){
        for(var j=1; j<n; j++){
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    
    return dp[m-1][n-1];
}

0 comments:

Blogroll

Follow this blog by Email

Popular Posts