 3/14/2018 - 7:22 AM

## rect-tl-to-bt

Count the number of ways to move from upper left corner of rectangle to bottom right.

a) Moving is possible to the left and to the right, b) Restricted to move right twice in a row

``````// Count the number of ways to move from upper left corner of rectangle to bottom right.
// a) Moving is possible to the left and to the right,

let numOfPaths = (m, n) => {
// create a 2D table to store results of subproblems
let count = [];

// count of paths to reach any cell in first column is 1
for (let i = 0; i < m; i++) count[i, 0] = 1;

// Count of paths to reach any cell in first column is 1
for (let j = 0; j < n; j++) count[0, j] = 1;

// Calculate count of paths for other cells in bottom-up manner using
// the recursive solution
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
// by uncommenting the last part the code calculatest he total
// possible paths if the diagonal movements are allowed
count[i, j] = count[i-1, j] + count[i, j-1]; // + count[i-1, j-1];
}
}
return count[m-1, n-1];
}

console.log('number of paths: ', numOfPaths(4, 4));``````