Pascal's Triangle

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

Construir cada fila a partir de la anterior lleva un tiempo de O(n²) para n filas, porque el triángulo tiene aproximadamente n²/2 entradas y cada una requiere una sola suma. Eso es óptimo, ya que tienes que escribir todas las entradas de la salida. Aparte de la salida, usa un espacio extra de O(1) .

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

La entrada k de la fila r , contando ambas desde 0, es el coeficiente binomial C(r, k) , el número de maneras de elegir k elementos de un total de r . La regla de que cada entrada es la suma de las dos que tiene encima es la identidad C(r, k) = C(r-1, k-1) + C(r-1, k) . Esa también es la razón por la que la fila r suma 2^r .

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 O(r) tiempo y ninguna otra fila.

Q: ¿Por qué el triángulo de Pascal es un problema de programación dinámica?

Cada entrada depende de dos subproblemas más pequeños, las entradas que están por encima de ella, y esos subproblemas se solapan mucho: la recursión simple los vuelve a calcular una y otra vez. Construir las filas en orden almacena cada subproblema una sola vez y lo reutiliza, lo que convierte un trabajo exponencial en O(n²) .

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, comienza 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, con la fila superior primero 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 numRows filas, con la fila superior primero

Restricciones

1 ≤ numRows ≤ 30
Cada entrada de las primeras 30 filas cabe en un entero con signo de 32 bits. La mayor 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 interior suma las dos que tiene encima. En la cuarta fila, 3 = 1 + 2 y 3 = 2 + 1. En la quinta fila, 4 = 1 + 3, 6 = 3 + 3 y 4 = 3 + 1.

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

+13 pruebas ocultas al enviar

Para ir más allá

¿Puedes construir solo la última fila en una única matriz, actualizándola in situ fila tras fila en lugar de conservar las filas anteriores? ¿En qué dirección debe avanzar 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

La regla que define el triángulo es recursiva: 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 una y otra vez, y el trabajo se duplica con cada fila. Las filas que te piden devolver son exactamente las respuestas almacenadas a esos problemas más pequeños, así que construye el triángulo de arriba abajo y lee cada fila de la que construiste antes.

Calcula cada entrada de forma recursiva

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

Intuición

Numera las filas y las posiciones dentro de una fila empezando por 0. La definición del triángulo se convierte en una función: entry(row, col) es 1 cuando col es 0 o igual a row, los dos bordes, y, en caso contrario, es entry(row-1, col-1) + entry(row-1, col). Llámala para cada posición de cada fila y tendrás el triángulo. Es correcto porque es la definición, palabra por palabra.

El problema es la cantidad de llamadas que hace. La recursión solo se detiene en los bordes, donde devuelve 1, así que calcular una entrada con valor v requiere unas 2v llamadas. La fila r suma hasta 2^r, así que las 30 filas en conjunto requieren unas 2^31 llamadas, más de dos mil millones. Las mismas entradas pequeñas se vuelven a calcular millones de veces: entry(2, 1) aparece debajo de casi todos los valores que hay por debajo.

Algoritmo

Escribe entry(row, col): devuelve 1 si col es 0 o 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 de arriba

Intuición

La versión recursiva sigue solicitando entradas de filas anteriores, y de todos modos ya estás construyendo esas filas. Así que calcula las filas en orden, de arriba abajo, y cuando rellenes la fila r, lee los valores que necesitas directamente de la fila r-1, que ya está lista. Cada entrada requiere entonces una suma. Esto es programación dinámica en su forma más sencilla: la tabla de respuestas más pequeñas es el propio resultado.

Empieza la fila r con r + 1 unos, lo que establece ambos extremos. Luego, para cada posición interior c desde 1 hasta r-1, asígnale above[c-1] + above[c]. Las filas 0 y 1 no tienen posiciones interiores, así que quedan como [1] y [1, 1] sin necesidad de un caso especial.

El triángulo tiene 1 + 2 + ... + n, aproximadamente n²/2, entradas, y cada una requiere un tiempo constante, así que el trabajo es O(n²). Aparte del resultado, que de todos modos tienes que devolver, el método no necesita memoria adicional. Para numRows = 30, eso supone 465 entradas 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

Los bucles son cortos, así que los errores tienen que ver con los límites y con las primeras filas.

Devolver numRows + 1 filas. Si numeras las filas desde 0, la última que necesitas es la fila numRows-1.
Ejecutar el bucle interno sobre los bordes. La posición 0 no tiene padre izquierdo y la posición row no tiene padre derecho, así que leer above[col-1] o above[col] allí se sale de los límites. Rellena solo las posiciones 1 a row-1.
Escribir un rango que falla con las 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. Protégelos o empieza las posiciones internas con unos para que las filas 0 y 1 no necesiten un bucle.
Calcular las entradas con factoriales. C(29, 14) cabe en un int, pero 29! desborda incluso un entero de 64 bits, así que una fórmula basada en factoriales imprime números incorrectos en las filas inferiores.
Reutilizar un mismo arreglo para todas las filas. Si añades el mismo arreglo cada vez y luego lo cambias, todas las filas de la respuesta terminan siendo iguales a la última.

Preguntas frecuentes4

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

Construir cada fila a partir de la anterior lleva un tiempo de O(n²) para n filas, porque el triángulo tiene aproximadamente n²/2 entradas y cada una requiere una sola suma. Eso es óptimo, ya que tienes que escribir todas las entradas de la salida. Aparte de la salida, usa un espacio extra de O(1).

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

La entrada k de la fila r, contando ambas desde 0, es el coeficiente binomial C(r, k), el número de maneras de elegir k elementos de un total de r. La regla de que cada entrada es la suma de las dos que tiene encima es la identidad C(r, k) = C(r-1, k-1) + C(r-1, k). Esa también es la razón por la que la fila r suma 2^r.

¿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 O(r) tiempo y ninguna otra fila.

¿Por qué el triángulo de Pascal es un problema de programación dinámica?

Cada entrada depende de dos subproblemas más pequeños, las entradas que están por encima de ella, y esos subproblemas se solapan mucho: la recursión simple los vuelve a calcular una y otra vez. Construir las filas en orden almacena cada subproblema una sola vez y lo reutiliza, lo que convierte un trabajo exponencial en O(n²).

Python

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

Casos de prueba

Caso 1

Caso 2

Entrada

numRows = 5

Esperado

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