Calcular nCr usando el Triángulo de Pascal

Una aplicación útil del triángulo de Pascal es el cálculo de combinaciones . La fórmula para encontrar ⁿ C _r es n! / r! * (n – r)! que es también la fórmula para una celda del triángulo de Pascal. 
Triángulo de Pascal: 
 

Input: n = 5, r = 3
Output: 10
Explanation:
n! / r! * (n - r)! = 5! / 3! * (2!) = 120 / 12 = 10

Input: n = 7, r = 2
Output: 21
Explanation:
n! / r! * (n - r)! = 7! / 5! * (2!) = 42 / 2 = 21

Enfoque: La idea es almacenar el triángulo de Pascal en una array, entonces el valor de ⁿ C _r será el valor de la celda en ^la fila n y ^la columna  r .
Para crear el triángulo pascal usa estas dos fórmulas: 
 

1. ⁿ C ₀ = 1 , el número de formas de seleccionar 0 elementos de un conjunto de n elementos es 0
2. ⁿ C _r = ^n-1 C _r-1 + ^n-1 C _r , número de formas de seleccionar r elementos de un conjunto de n elementos es la suma de formas de seleccionar r-1 elementos de n-1 elementos y formas de seleccionar r elementos de n-1 elementos.

La idea es usar los valores de los subproblemas para calcular las respuestas para valores más grandes. Por ejemplo, para calcular ⁿ C _r , use los valores de ^n-1 C _r-1 y ^n-1 C _r . Entonces, DP se puede usar para preprocesar todos los valores en el rango.
Algoritmo: 
 

1. Cree una array de tamaño 1000 * 1000, asigne el valor de los casos base, es decir, ejecute un ciclo de 0 a 1000 y asigne array[i][0] = 1, ⁿ C ₀ = 1
2. Ejecute un ciclo anidado de i = 1 a 1000 (bucle externo) y el ciclo interno se ejecuta de j = 1 a i + 1.
3. Para cada elemento (i, j) asigne el valor de array[i][j] = array[i-1][j-1] + array[i-1][j] , usando la fórmula ⁿ C _r = ^{n -1} C _r-1 + ^n-1 C _r
4. Después de llenar la array, devuelve el valor de ⁿ C _r como array[n][r]

Implementación: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Initialize the matrix with 0
int l[1001][1001] = { 0 };
 
void initialize()
{
 
    // 0C0 = 1
    l[0][0] = 1;
    for (int i = 1; i < 1001; i++) {
        // Set every nCr = 1 where r = 0
        l[i][0] = 1;
        for (int j = 1; j < i + 1; j++) {
 
            // Value for the current cell of Pascal's triangle
            l[i][j] = (l[i - 1][j - 1] + l[i - 1][j]);
        }
    }
}
 
// Function to return the value of nCr
int nCr(int n, int r)
{
    // Return nCr
    return l[n][r];
}
 
// Driver code
int main()
{
    // Build the Pascal's triangle
    initialize();
    int n = 8;
    int r = 3;
    cout << nCr(n, r);
}
 
// This code is contributed by ihritik

// Java implementation of the approach
 
class GFG {
    // Initialize the matrix with 0
    static int l[][] = new int[1001][1001];
 
    static void initialize()
    {
 
        // 0C0 = 1
        l[0][0] = 1;
        for (int i = 1; i < 1001; i++) {
            // Set every nCr = 1 where r = 0
            l[i][0] = 1;
            for (int j = 1; j < i + 1; j++) {
 
                // Value for the current cell of Pascal's triangle
                l[i][j] = (l[i - 1][j - 1] + l[i - 1][j]);
            }
        }
    }
 
    // Function to return the value of nCr
    static int nCr(int n, int r)
    {
        // Return nCr
        return l[n][r];
    }
    // Driver code
    public static void main(String[] args)
    {
        // Build the Pascal's triangle
        initialize();
        int n = 8;
        int r = 3;
        System.out.println(nCr(n, r));
    }
}
 
// This code is contributed by ihritik

# Python3 implementation of the approach
 
# Initialize the matrix with 0
l = [[0 for i in range(1001)] for j in range(1001)]
 
def initialize():
     
    # 0C0 = 1
    l[0][0] = 1
    for i in range(1, 1001):
         
        # Set every nCr = 1 where r = 0
        l[i][0] = 1
        for j in range(1, i + 1):
             
            # Value for the current cell of Pascal's triangle
            l[i][j] = (l[i - 1][j - 1] + l[i - 1][j])
 
# Function to return the value of nCr
def nCr(n, r):
    # Return nCr
    return l[n][r]
 
# Driver code
# Build the Pascal's triangle
initialize()
n = 8
r = 3
print(nCr(n, r))

// C# implementation of the approach
 
using System;
class GFG {
    // Initialize the matrix with 0
    static int[, ] l = new int[1001, 1001];
 
    static void initialize()
    {
 
        // 0C0 = 1
        l[0, 0] = 1;
        for (int i = 1; i < 1001; i++) {
            // Set every nCr = 1 where r = 0
            l[i, 0] = 1;
            for (int j = 1; j < i + 1; j++) {
 
                // Value for the current cell of Pascal's triangle
                l[i, j] = (l[i - 1, j - 1] + l[i - 1, j]);
            }
        }
    }
 
    // Function to return the value of nCr
    static int nCr(int n, int r)
    {
        // Return nCr
        return l[n, r];
    }
    // Driver code
    public static void Main()
    {
        // Build the Pascal's triangle
        initialize();
        int n = 8;
        int r = 3;
        Console.WriteLine(nCr(n, r));
    }
}
 
// This code is contributed by ihritik

<script>
 
// JavaScript implementation of the approach
 
// Initialize the matrix with 0
let l =
new Array(1001).fill(0).map(() => new Array(1001).fill(0));
 
function initialize()
{
 
    // 0C0 = 1
    l[0][0] = 1;
    for (let i = 1; i < 1001; i++) {
        // Set every nCr = 1 where r = 0
        l[i][0] = 1;
        for (let j = 1; j < i + 1; j++) {
 
            // Value for the current cell
            // of Pascal's triangle
            l[i][j] = (l[i - 1][j - 1] + l[i - 1][j]);
        }
    }
}
 
// Function to return the value of nCr
function nCr(n, r)
{
    // Return nCr
    return l[n][r];
}
 
// Driver code
 
    // Build the Pascal's triangle
    initialize();
    let n = 8;
    let r = 3;
    document.write(nCr(n, r));
 
// This code is contributed by Mayank Tyagi
 
</script>

56

Análisis de Complejidad: 
 

• Complejidad Temporal: O(1). 
  El valor de todos los pares se calcula previamente, por lo que el tiempo para responder a la consulta es O (1), aunque se tarda algo de tiempo en el cálculo previo, pero teóricamente el cálculo previo lleva un tiempo constante.
• Complejidad espacial: O(1). 
  Se requiere espacio constante.