leetcode-program

Question 62: Unique Paths

Link

Solution

m + n - 2 steps in total, n - 1 of them should be right directions. Therefore, the answer is C(m + n - 2, n - 1).

Code

Java

public class Solution {
    private static int[][] C = new int[201][201];

    public int uniquePaths(int m, int n) {
        return computeC(m + n - 2, n - 1);
    }

    private static int computeC(int b, int u) {
        if (u == 0 || b == u) return 1;
        if (C[b][u] != 0) return C[b][u];
        return C[b][u] = computeC(b - 1, u) + computeC(b - 1, u - 1);
    }
}

This site is open source. Improve this page.