/**
 * For this question, we could use back-tracing to go trough each cell and sum 
 *     up the results then use Dynamic Programming to cache the result to save 
 *     time.
 *
 * For m*n grid, the robot need to go m-1 steps down and n-1 steps right, total
 *     (m+n-2) steps. However, go down and go left is accordingly independent, 
 *     we could go either direction at any step. Then it become to pick n-1 
 *     from (m+n-2). It's just math, calculate the combination.
 *
 * 
 * With DP, the run time is O(m*n), and space complexity could be reduced to
 *     O(min(m, n)). But with combination, it only take O(min(m, n)) time and 
 *     O(1) space. MATHEMATICS is bug.
 */ 

#include <iostream>

using namespace std;

/**
 * Calculate k combinations of set n
 *
 * r = n!/(k! * (n-k)!)
 */
int Combination(int k, int n) 
{
    if (n/2 < k) k = n-k;
    
    long long r = 1;
    for (int i = 0; i < k; ++i) 
        r = r * (n-i) / (i+1);
    
    return r;
}

int UniquePaths(int m, int n)
{
    int dp[n][m];
    //initialize the margin
    for (int i = 0; i < n; ++i)
        dp[i][m-1] = 1;
    for (int j = 0; j < m; ++j)
        dp[n-1][j] = 1;
    
    for (int i = n-2; i >=0; --i)
        for (int j = m-2; j >=0; --j)
            dp[i][j] = dp[i+1][j] + dp[i][j+1];
    
    return dp[0][0];
}


int main(int argc, char** argv)
{
    int limit = 10;
    for (int i = 2; i < limit; ++i)
    {
        for (int j = 2; j < limit; ++j)
        {
            printf("%d, %d :    ", i, j);
            cout << UniquePaths(j, i) << "    ";
            cout << Combination(i-1, (i+j-2)) << endl;
        }
        
    }
    
    return 0;
}