Ian Dorian Macleod
Problem 14
Problem Statement

Starting in the top left corner of a 2x2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20x20 grid?

Approach

C++ implementation

#include <stdc++.h>
using namespace std;

long long int paths(int n) {
vector> ans;
for (int i = 0; i <= n; i++) {
ans.push_back(vector(n+1, 0));
}
ans[0][0] = 1;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
if (i) ans[i][j] += ans[i-1][j];
if (j) ans[i][j] += ans[i][j-1];
}
}
return ans[n][n];
}

int main() {

cout << paths(20) << endl;
return 0;

}


You can also download the source code for this problem here and compile it on your local machine.
Further Analysis