Project Euler #15 - Lattice paths

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?

출처: https://projecteuler.net/

20*20 격자에서 좌측 상단에서 우측 상단까지 가는 경로의 개수를 구하는 문제입니다. (최소 경로)

완전 탐색보다 나은 방법을 고민하다 20 x 20 즉 40개의 칸에서 20개의 길을 선택하는 문제이기에 이항계수로 풀면 되겠다는 생각이 들었습니다. 이항 계수는 재귀함수와 memoization 을 사용해 시간 복잡도를 줄이는 방법을 사용했습니다.

my solving

c++

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
typedef long long ll;
 
ll cache[50][50];
 
ll getBinomialCoefficient(int n, int k)
{
    ///모든 원소를 다 고르는 경우 또는 고를 원소가 없는 경우
    if (n == k || k == 0)
        return 1;
 
    if (cache[n][k] != -1)
        return cache[n][k];
 
    return cache[n][k] = getBinomialCoefficient(n - 1, k - 1) + getBinomialCoefficient(n - 1, k);
}
 
int main() 
{
    memset(cache, -1, sizeof(cache));
    cout << getBinomialCoefficient(40,20) << endl;
 
    system("pause");
    return 0;
}

-------------------------------------------------------------

Recursive formula[edit]

One method uses the recursive, purely additive, formula

with initial/boundary values

The formula follows from considering the set {1,2,3,…,n} and counting separately (a) the k-element groupings that include a particular set element, say “i”, in every group (since “i” is already chosen to fill one spot in every group, we need only choose k − 1 from the remaining n − 1) and (b) all the k-groupings that don’t include “i”; this enumerates all the possible k-combinations of n elements. It also follows from tracing the contributions to X^k in (1 + X)ⁿ⁻¹(1 + X). As there is zero Xⁿ⁺¹ or X⁻¹ in (1 + X)ⁿ, one might extend the definition beyond the above boundaries to include  = 0 when either k > n or k < 0. This recursive formula then allows the construction of Pascal's triangle, surrounded by white spaces where the zeros, or the trivial coefficients, would be.

출처: https://en.wikipedia.org/wiki/Binomial_coefficient