(This question has been seen in the interviews of the following companies: Google)

Given the length and width of a matrix, get the number of paths from bottom-left to bottom right.

You may only walk into those 3 directions ➡ (right) ↗ (upper-right) ↘ (lower-right) at each point.

Follow-up: optimize 2d DP to 1d DP of linear extra space.

Follow-up: what if some cells are blocked

```
public class MatrixPuzzle {
int column;
int row;
public MatrixPuzzle(int length, int width) {
this.column = length;
this.row = width;
}
//The dp formula will be M[i,j] = M[i - 1, j - 1] + M[i - 1, j] + M[i - 1, j + 1]
//Because one could only land on current cell from the 3 cells in the upper-left, left and lower-left.
//To make the space consumption 1d, cache the numbers in one column of the matrix at a time.
//Follow-up 2: Just reset path-counts for blocked cells to 0
public int numberOfPaths() {
int[] paths = new int[row];
paths[row - 1] = 1; //start from bottom-left corner
for(int col = 1; col < column; col++) {
int upper_left_value = 0;
for(int r = 0; r < row; r++) {
int left_value = paths[r];
paths[r] += upper_left_value + (r == row - 1 ? 0 : paths[r + 1]);
upper_left_value = left_value;
}
}
return paths[row - 1]; //exit from bottom-right
}
}
```

#### Get one-to-one training from Google Facebook engineers

##### Top-notch Professionals

Learn from Facebook and Google senior engineers interviewed 100+ candidates.

Most recent interview questions and system design topics gathered from aonecode alumnus.

One-to-one online classes. Get feedbacks from real interviewers.

##### Customized Private Class

Already a coding expert? - Advance straight to hard interview topics of your interest.

New to the ground? - Develop basic coding skills with your own designated mentor.

Days before interview? - Focus on most important problems in target company question bank.