/**
 * A robot is located at the top-left corner of a m x n grid.
 * The robot can only move either down or right at any point in time.
 * The robot is trying to reach the bottom-right corner of the grid.
 * 
 * How many possible unique paths are there?
 * 
 * Solution by DP
 * 
 * Solution by combination:
 * This problem is equivalent to put m-1 items into n-1 boxes,
 * in which empty boxes are allowed. Treat each box as an item,
 * then this problem is equivalent to select n-1 items (boxes)
 * out of m + n - 2 items. Pure mathematical calculation.
 * 
 */

public class UniquePaths {
    // solve by DP
    public int uniquePaths(int m, int n) {
        int[][] result = new int[m][n];
        // the final row and column has only one choice to the terminal
        for (int i = 0; i < m; ++i) result[i][n-1] = 1;
        for (int j = 0; j < n; ++j) result[m-1][j] = 1;
        // the number of ways to get to terminal for any inner cell
        // depends on its right and underlying neighbors
        for (int i = m-2; i >= 0; --i) {
            for (int j = n-2; j >= 0; --j) {
                result[i][j] = result[i+1][j] + result[i][j+1];
            }
        }
        return result[0][0];
    }
    
    // solve by combination
    public long uniquePathsCombination(int m, int n) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int maxParam = Math.max(m, n);
        int minParam = Math.min(m, n);
        return Combination(maxParam + minParam - 2, minParam - 1);
    }
    
    private static long Combination(int n, int m) {
        if (m == 0) return 1;
        else if (m == 1) return n;
        long result = 1;
        for (int i = 0; i < m; i++) {
            result = result * (n - i) / (i + 1);
        }
        return result;
    }
}