Dynamic programming

We know that at each step, you can either come from left or top. If we record how many ways to reach the left and reach the top, the current possible steps = possible steps to reach left + possible steps to reach right.

We init the left and top margin to 1 since there is only 1 way to reach each tile on it.

        std::vector<std::vector<int>> steps(m, vector<int> (n, 0));
        for (int i = 0; i < m; i ++){
            steps[i][0] = 1;
        }
        for (int i = 0; i < n; i ++){
            steps[0][i] = 1;
        }

        for (int i = 1; i < m; i ++){
            for (int j = 1; j < n; j ++){
                steps[i][j] = steps[i - 1][j] + steps[i][j - 1];
            }
        }
        return steps[m - 1][n - 1];
    }

Combinatorics

For each down-right path(actually just a flipped north east lattice), we have total of n + m steps. But if you have chosen all your horizontal moves(n of them), then the vertical moves are decided as well. There are (n + m) choose n ways to pick horizontal moves.

Actually it doesn’t matter if you pick all horizontal or all vertical first, because n choose m = n choose n -m ( since choosing m element out of n is equal to choosing m’s complement, n – m, out of n.

Recall the formula for n choose k. .

Need to subtract 1 from both m and n

Because we start from (1,1) so there are only m – 1 and n – 1 steps on each direction

Time out for factorial

return fact(n + m) / (fact(m) * fact(n)) ;

Doesn’t work because of overflow. But we can keep the size in check by cancelling the first m factorial in fact(n + m) with fact(m). Then starting (m + 1)*(m + 2)…(m + n). but also in each step, we divide it by j. j is component of n!.

    int uniquePaths(int m, int n) {
        n--;
        m--;
        long long prod = 1;
        int j = 1;
        for (int i = m + 1; i < n + m + 1; i ++){
            prod *= i;
            if (i - m < n + 1){
                prod /= j;
                j ++;
            }

        }
        return prod;