Skip to main content
Code Review

Return to Question

Tweeted twitter.com/StackCodeReview/status/1018147673285816320
edited tags; edited title
Link
200_success
200_success
  • 145.7k
  • 22
  • 191
  • 481

Project Euler #15 (Dynamic C++): counting paths through a 20 × 20 grid

added mathjax formatting
Source Link
Edward
Edward
  • 67.2k
  • 4
  • 120
  • 284

I've recently solved Project Euler's 15th problem stating:

Starting in the top left corner of a 2×2 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 20×20 grid?

This is my dynamic approach in C++

#include <cstdio> const unsigned short n = 20; int main() { unsigned long long p[n][n]; for (unsigned short i = 2; i <= n; i++) p[n - i][n - 1] = i + 1; for (unsigned short i = n - 2; i >= 1; i--) { p[i][i] = 2 * p[i][i + 1]; for (unsigned short k = i; k >= 1; k--) p[k - 1][i] = p[k][i] + p[k - 1][i + 1]; } printf("%llu", 2 * p[0][1]); }

I am aware that this problem could be solved way more efficiently and faster by simply calculating (2n)! / (n!)^2\${(2n)!}/{(n!)^2}\$, however I decided to look at this problem from a programmer's point of view, rather than a mathematician's.

I've recently solved Project Euler's 15th problem stating:

Starting in the top left corner of a 2×2 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 20×20 grid?

This is my dynamic approach in C++

#include <cstdio> const unsigned short n = 20; int main() { unsigned long long p[n][n]; for (unsigned short i = 2; i <= n; i++) p[n - i][n - 1] = i + 1; for (unsigned short i = n - 2; i >= 1; i--) { p[i][i] = 2 * p[i][i + 1]; for (unsigned short k = i; k >= 1; k--) p[k - 1][i] = p[k][i] + p[k - 1][i + 1]; } printf("%llu", 2 * p[0][1]); }

I am aware that this problem could be solved way more efficiently and faster by simply calculating (2n)! / (n!)^2, however I decided to look at this problem from a programmer's point of view, rather than a mathematician's.

I've recently solved Project Euler's 15th problem stating:

Starting in the top left corner of a 2×2 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 20×20 grid?

This is my dynamic approach in C++

#include <cstdio> const unsigned short n = 20; int main() { unsigned long long p[n][n]; for (unsigned short i = 2; i <= n; i++) p[n - i][n - 1] = i + 1; for (unsigned short i = n - 2; i >= 1; i--) { p[i][i] = 2 * p[i][i + 1]; for (unsigned short k = i; k >= 1; k--) p[k - 1][i] = p[k][i] + p[k - 1][i + 1]; } printf("%llu", 2 * p[0][1]); }

I am aware that this problem could be solved way more efficiently and faster by simply calculating \${(2n)!}/{(n!)^2}\$, however I decided to look at this problem from a programmer's point of view, rather than a mathematician's.

Source Link
Gentlebud
Gentlebud
  • 83
  • 6

Project Euler #15 (Dynamic C++)

I've recently solved Project Euler's 15th problem stating:

Starting in the top left corner of a 2×2 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 20×20 grid?

This is my dynamic approach in C++

#include <cstdio> const unsigned short n = 20; int main() { unsigned long long p[n][n]; for (unsigned short i = 2; i <= n; i++) p[n - i][n - 1] = i + 1; for (unsigned short i = n - 2; i >= 1; i--) { p[i][i] = 2 * p[i][i + 1]; for (unsigned short k = i; k >= 1; k--) p[k - 1][i] = p[k][i] + p[k - 1][i + 1]; } printf("%llu", 2 * p[0][1]); }

I am aware that this problem could be solved way more efficiently and faster by simply calculating (2n)! / (n!)^2, however I decided to look at this problem from a programmer's point of view, rather than a mathematician's.