Pascal's Triangle

Q: ¿Cuál es la complejidad temporal de generar el triángulo de Pascal?

O(n²) para n filas: el triángulo tiene aproximadamente n²/2 entradas y cada una requiere una suma. Esto es óptimo, ya que debes escribir todas las entradas de la salida. El espacio adicional, aparte de la salida, es O(1) .

Q: ¿Qué relación tiene el triángulo de Pascal con los coeficientes binomiales?

La entrada k de la fila r , contando desde 0, es C(r, k) , el número de maneras de elegir k elementos de entre r . La regla de la suma es la identidad C(r, k) = C(r-1, k-1) + C(r-1, k) , y la suma de la fila r es 2^r , el número de subconjuntos de r elementos.

Q: ¿Puedes calcular una fila sin construir las filas que están encima?

Sí. Empieza con 1 y obtén cada entrada siguiente a partir de la anterior: C(r, k) = C(r, k-1) × (r-k+1) / k . Multiplica antes de dividir para que la división sea exacta, y usa un entero de 64 bits para el producto. La fila r después requiere un tiempo O(r) .

FácilProgramación dinámica

+10

En el triángulo de Pascal, la primera fila es [1]. Cada fila posterior tiene una entrada más, empieza y termina con 1, y cada entrada intermedia es la suma de las dos entradas que tiene justo encima. Recibes un entero numRows. Devuelve las primeras numRows filas del triángulo, empezando por la fila superior, y cada fila como un arreglo de enteros.

Función

generate(numRows: integer) → integer-2d-array

numRowsinteger: cuántas filas del triángulo construir
Devuelveinteger-2d-array: las primeras filas de numRows, empezando por la fila superior

Restricciones

1 ≤ numRows ≤ 30
Cada entrada de las primeras 30 filas cabe en un entero con signo de 32 bits. La más grande es 77558760, en el centro de la fila 30.

Ejemplos

Entrada: numRows = 5
Salida: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
Explicación: Cada entrada interna suma las dos que están encima. Fila cuatro: 3 = 1 + 2 y 3 = 2 + 1. Fila cinco: 4 = 1 + 3, 6 = 3 + 3, 4 = 3 + 1.

Entrada: numRows = 1
Salida: [[1]]
Explicación: Con una fila, el triángulo es solo su parte superior, [1].

Para ir más allá

¿Puedes conservar un solo arreglo y actualizarlo en el lugar, fila tras fila? ¿En qué sentido debe ejecutarse el bucle interno y por qué?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Una entrada es la suma de dos entradas de la fila anterior. Evaluar esa regla desde cero para cada entrada vuelve a calcular los mismos valores, y el trabajo se duplica con cada fila. Las filas que devuelves son las respuestas almacenadas a esos problemas más pequeños, así que construye el triángulo de arriba abajo, cada fila a partir de la anterior.

Calcula cada entrada de forma recursiva

Correcto, pero no termina con las pruebas más grandes

Intuición

Numera las filas y las posiciones desde 0. La definición se convierte en una función: entry(row, col) es 1 en los bordes, donde col es 0 o row, y en caso contrario entry(row-1, col-1) + entry(row-1, col). Es correcta porque es la definición.

La recursión se detiene solo en los bordes, que devuelven 1, así que una entrada de valor v requiere aproximadamente 2v llamadas. La fila r suma hasta 2^r, así que 30 filas requieren aproximadamente 2^31 llamadas, más de dos mil millones.

Algoritmo

Escribe entry(row, col): devuelve 1 si col es 0 o si col es igual a row.
De lo contrario, devuelve entry(row-1, col-1) + entry(row-1, col).
Para cada row desde 0 hasta numRows-1, recopila entry(row, col) para cada col desde 0 hasta row.
Devuelve la lista de filas.

def pascalEntry(row, col):
    if col == 0 or col == row:
        return 1  # the edges of the triangle
    return pascalEntry(row - 1, col - 1) + pascalEntry(row - 1, col)


def generate(numRows):
    triangle = []
    for row in range(numRows):
        triangle.append([pascalEntry(row, col) for col in range(row + 1)])
    return triangle

Construye cada fila a partir de la fila anterior

Intuición

La recursión sigue solicitando entradas de filas anteriores, y aun así construyes esas filas. Así que calcula las filas de arriba abajo y, mientras llenas la fila r, lee la fila r-1, que ya está lista. Cada entrada requiere una suma: la tabla de respuestas más pequeñas es la propia salida.

Empezar cada fila con r + 1 unos establece ambos extremos, así que las filas 0 y 1, que no tienen posiciones interiores, no necesitan ningún caso especial. El triángulo tiene 1 + 2 + ... + n, aproximadamente n²/2, entradas, así que el trabajo es O(n²) sin usar memoria más allá de la salida: 465 entradas para 30 filas, en lugar de dos mil millones de llamadas.

Algoritmo

Empieza con una lista vacía de filas.
Para cada row desde 0 hasta numRows-1, crea row + 1 unos.
Para cada col desde 1 hasta row-1, asígnale la suma de las posiciones col-1 y col de la fila anterior.
Añade la fila y continúa. Devuelve la lista.

def generate(numRows):
    triangle = [[1]]
    for row in range(1, numRows):
        above = triangle[-1]
        values = [1] * (row + 1)  # both edges are 1
        for col in range(1, row):
            values[col] = above[col - 1] + above[col]
        triangle.append(values)
    return triangle

Errores comunes y casos límite

Devolver numRows + 1 filas. Numeradas desde 0, la última fila que necesitas es numRows-1.
Ejecutar el bucle interno sobre los bordes. La posición 0 no tiene padre a la izquierda y la posición row no tiene uno a la derecha, así que leerlos provoca un acceso fuera de los límites.
Un rango que falla con filas pequeñas. Swift's 1..<row falla cuando row es 0, y R's 2:(row-1) cuenta hacia atrás hasta 1 cuando row es 2.
Calcular los elementos usando factoriales. C(29, 14) cabe en un int, pero 29! desborda incluso un entero de 64 bits.
Añadir el mismo array en cada fila y luego modificarlo. Todas las filas de la respuesta terminan siendo la última.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de generar el triángulo de Pascal?

O(n²) para n filas: el triángulo tiene aproximadamente n²/2 entradas y cada una requiere una suma. Esto es óptimo, ya que debes escribir todas las entradas de la salida. El espacio adicional, aparte de la salida, es O(1).

¿Qué relación tiene el triángulo de Pascal con los coeficientes binomiales?

La entrada k de la fila r, contando desde 0, es C(r, k), el número de maneras de elegir k elementos de entre r. La regla de la suma es la identidad C(r, k) = C(r-1, k-1) + C(r-1, k), y la suma de la fila r es 2^r, el número de subconjuntos de r elementos.

¿Puedes calcular una fila sin construir las filas que están encima?

Sí. Empieza con 1 y obtén cada entrada siguiente a partir de la anterior: C(r, k) = C(r, k-1) × (r-k+1) / k. Multiplica antes de dividir para que la división sea exacta, y usa un entero de 64 bits para el producto. La fila r después requiere un tiempo O(r).

def generate(numRows):
    # Escribe el código aquí

Prueba #1

Prueba #2

Argumento

numRows = 5

Salida Esperada

[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]