015.cpp

Go to the documentation of this file.

#include <iostream>
using namespace std;


/*
Can use recursion but very inefficient:
unsigned route(int a, int b)
{
if(a==0) return 1;
if(b==0) return 1;
return route(a-1,b)+route(a,b-1);
}
cout << route(20,20);
*/
int 
main(){

 int grid = 20;
  unsigned long long matrix[grid+1][grid+1];
  matrix[0][0] = 1;
  for (int i = 1; i <= grid; i++)
    {
      matrix[0][i] = 1;
      matrix[i][0] = 1;
    }

  for (int i = 1; i <= grid; i++)
    for (int j = 1; j <= grid; j++)
      matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1];

  cout << matrix[grid][grid] << endl;
  return 0;
}