LC62. Unique Paths

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. \frac{n!}{k!(n - 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;

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax