Combinação simples (Triângulo de Pascal)

SimpleCombination

// Cálculo de combinação simples utilizando o triângulo de Pascal, onde:
//
//   Relação de Stifel
//   
//   | n-1 | + | n-1 | = | n |
//   | k-1 |   | k   |   | k |
//
// Ex.: Quantidade de jogos da Mega Sena
//      var quantity = SimpleCombination(60, 6);
//
// Simples de fazer, mas com alta complexidade!
// Experimente calcular algo como SimpleCombination(60, 15) ;P
int SimpleCombination(int n, int p)
{
    if((n == 0) || (p == 0) || (p == n))
        return 1;

    return SimpleCombination(n - 1, p - 1) + SimpleCombination(n - 1, p);
}

SimpleCombinationDynamic

// Solução para o Triângulo de Pascal de forma otimizada
// 
// 60 choose 15 = 53194089192720     (0ms)
// 60 choose 30 = 118264581564861424 (0ms)
// 
public long SimpleCombination(int n, int p)
{
    return SimpleCombination(n, p, new long[n + 1, p + 1]);
}

public long SimpleCombination(int n, int p, long[,] dp)
{
    if ((n == 0) || (p == 0) || (n == p))
        return 1;

    if (dp[n, p] == 0)
        dp[n, p] = SimpleCombination(n - 1, p - 1, dp) + SimpleCombination(n - 1, p, dp);

    return dp[n, p];
}