Leetcode diary: 62. Unique Paths

This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.

link

This one I gave up on the first time and looked at solution. After a week I came back today and was happily able to solve it pretty fast. It really means that I understood the problem at hand and did not just straight up memorize the solution.

The question is given a m by n matrix, how many unique ways you could go from the top left to bottom right of the matrix. Note that you could only go down or right each time you make a move.

So this is pretty similar to the previous questions I have done recently. So the first thing we should do is see if we can break down the problem to subproblems and see if incremental progression can lead to a solution.

The trick at hand is that:
1.) for the first row, matrix[0], all of the values are 1. This is because once we move out of the first row, we can't go back; only down and right moves are allowed. So there is only one way to get to any of the first row: by moving right constantly.
2.) similarly, first index of any row, matrix[i][0] is 1 as well.
3.) For any matrix[i][j] the number of ways we can get to it is by down or right move. This means that we can only get to (i,j) from (i-1,j) OR (i,j-1). The or statement, if you recall from math a long time ago, means additions in the context.
Therefore the number of ways to get to (i,j) = #(i-1,j) + #(i,j-1).

Starting at (1,1), this means #(i-1,j) + #(i,j-1) = #(0,1) + #(1,0) = 2. You can try it out yourself. We can progress forward in this fashion until the bottom right of the matrix:

var uniquePaths = function(m, n) {
    const memo = new Array(m);
    for (let i=0; i < m; i++) {
        memo[i] = new Array(n);
        memo[i][0] = 1;
    };

    memo[0].fill(1);

    for (let i=1; i <m; i++) {
        for (let j=1; j<n; j++) {
            memo[i][j] = memo[i-1][j] + memo[i][j-1];
        }
    }

    return memo[m-1][n-1]
}

Let me know anything on your mind after reading through this, THANKS!