[tabby title=”Task”]

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?

 m = 3, n = 2

 3

From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

 m = 7, n = 3

 28

This problem was taken from Leetcode unique paths and Leetcode_unique_paths_part_II

[tabby title=”Solution”]

Since we can move only right or down on every cell in the first row we will have only one place from where we can come and this is the cell before. And same for the first vertical row.

Then after we figured out that there is only one way to reach each cell in the first row and the first column (which is from the cell before) we could start calculating possible ways to go to the next cells.
Let’s look at the cell in the second row and second column.There are actually two possible ways to go there: from the cell above, and the cell before, so 2 possible ways. (figure below).
The cell in the third column on the second row: same 1 way from the cell above, and from the cell before. But since there are already 2 ways to reach the cell before the total ways to reach this cell is: 1 + 2 = 3.

The solution:

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    
    var memo = [];

    for(var i=0;i < n; i ++) {
        for(var j = 0; j < m; j ++) {
            var index = (i * m) + j; 
            if(i == 0) {
                memo[index] = 1;
            }
            else if(j == 0) {
                memo[index] = 1;
            }
            else {
                var up = index - m;
                var left = index - 1;
                memo[index] = memo[up] + memo[left];
            }
        }
    }
    return memo[memo.length - 1];
}

console.log(uniquePaths(7,3));

Unique paths with obstacles.

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function(obstacleGrid) {
    var m = obstacleGrid[0].length;
    var n = obstacleGrid.length;
    var row = 0;
    if(obstacleGrid[0][0] == 1)
        return 0;

    var memo = [];

    for(var i=0;i < n; i ++) {
        for(var j = 0; j < m; j ++) {
            var index = (i * m) + j; 
            if(i == 0) {
                if(obstacleGrid[i][j] == 1 || (j > 0 && memo[index -1] == 0))
                    memo[index] = 0;
                else                
                    memo[index] = 1;
            }
            else if(j == 0) {
                if(obstacleGrid[i][j] == 1 || (i > 0 && memo[index - m] == 0))
                    memo[index] = 0;
                else                
                    memo[index] = 1;
            }
            else {
                var up = index - m;
                var left = index - 1;
                if(obstacleGrid[i][j] == 1)
                    memo[index] = 0;
                else
                    memo[index] = memo[up] + memo[left];
            }
            row += memo[index] ? 0 : 1;
        }
        if(row == m)
            return 0;            
        row = 0;
    }
    return memo[memo.length - 1];
};


var grid = [
  [0,0,0],
  [0,1,0],
  [0,0,0]
];

console.log(uniquePathsWithObstacles(grid));

[tabbyending]