Pascal's Triangle

Q: Qual è la complessità temporale della generazione del triangolo di Pascal?

Costruire ogni riga a partire da quella sopra richiede un tempo pari a O(n²) per n righe, perché il triangolo contiene circa n²/2 elementi e ciascuno richiede una sola addizione. È ottimale, perché devi scrivere ogni elemento dell'output. A parte l'output, usa O(1) spazio aggiuntivo.

Q: Qual è la relazione tra il triangolo di Pascal e i coefficienti binomiali?

La voce k della riga r , contando entrambe da 0, è il coefficiente binomiale C(r, k) , il numero di modi per scegliere k elementi tra r . La regola secondo cui ogni voce è la somma delle due soprastanti è l’identità C(r, k) = C(r-1, k-1) + C(r-1, k) . È anche per questo che la somma degli elementi della riga r è 2^r .

Q: Riesci a calcolare una riga senza costruire le righe che la precedono?

Sì. Inizia con 1 e ricava ogni voce successiva da quella precedente: C(r, k) = C(r, k-1) × (r-k+1) / k . Moltiplica prima di dividere, così la divisione è esatta, e usa un intero a 64 bit per il prodotto. La riga r richiede quindi O(r) di tempo e nessun’altra riga.

Q: Perché il triangolo di Pascal è un problema di programmazione dinamica?

Ogni voce dipende da due sottoproblemi più piccoli, le voci che la precedono, e questi sottoproblemi si sovrappongono ampiamente: la ricorsione semplice li ricalcola continuamente. Costruire le righe in ordine memorizza ogni sottoproblema una sola volta e lo riutilizza, trasformando un lavoro esponenziale in O(n²) .

FacileProgrammazione dinamica

+10

Nel triangolo di Pascal, la prima riga è [1]. Ogni riga successiva contiene un elemento in più, inizia e finisce con 1 e ogni elemento intermedio è la somma dei due elementi direttamente sopra di esso. Ricevi un intero numRows. Restituisci le prime numRows righe del triangolo, partendo dalla riga superiore, con ogni riga come array di interi.

Funzione

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

numRowsinteger: quante righe del triangolo costruire
Restituisceinteger-2d-array: le prime numRows righe, iniziando dalla riga in alto

Vincoli

1 ≤ numRows ≤ 30
Ogni voce delle prime 30 righe rientra in un intero con segno a 32 bit. La più grande è 77558760, al centro della riga 30.

Esempi

Input: numRows = 5
Output: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
Spiegazione: Ogni elemento interno somma i due che ha sopra. Nella quarta riga, 3 = 1 + 2 e 3 = 2 + 1. Nella quinta riga, 4 = 1 + 3, 6 = 3 + 3 e 4 = 3 + 1.

Input: numRows = 1
Output: [[1]]
Spiegazione: Con una riga, il triangolo è solo la sua cima, [1].

+13 test nascosti all’invio

Per approfondire

Puoi costruire solo l’ultima riga in un singolo array, aggiornandola sul posto riga dopo riga invece di mantenere le righe precedenti? In quale direzione deve procedere il ciclo interno e perché?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

La regola che definisce il triangolo è ricorsiva: un elemento è la somma di due elementi della riga soprastante. Valutare quella regola da zero per ogni elemento ricalcola gli stessi valori più e più volte, e il lavoro raddoppia a ogni riga. Le righe che devi restituire sono esattamente le risposte memorizzate a quei problemi più piccoli, quindi costruisci il triangolo dall’alto verso il basso e ricava ogni riga da quella che hai costruito prima.

Calcola ogni elemento in modo ricorsivo

Corretto, ma non termina sui test più grandi

Intuizione

Numera le righe e le posizioni all’interno di una riga partendo da 0. La definizione del triangolo diventa una funzione: entry(row, col) è 1 quando col è 0 o uguale a row, i due bordi, e altrimenti è entry(row-1, col-1) + entry(row-1, col). Chiamala per ogni posizione di ogni riga e otterrai il triangolo. È corretto perché è la definizione, parola per parola.

Il problema è il numero di chiamate che effettua. La ricorsione si ferma solo ai bordi, dove restituisce 1, quindi per calcolare una voce di valore v servono circa 2v chiamate. La riga r totalizza fino a 2^r, quindi per le 30 righe servono in tutto circa 2^31 chiamate, più di due miliardi. Le stesse piccole voci vengono ricalcolate milioni di volte: entry(2, 1) si trova sotto quasi ogni valore che sta più in basso.

Algoritmo

Scrivi entry(row, col): restituisci 1 se col è 0 o se col è uguale a row.
Altrimenti, restituisci entry(row-1, col-1) + entry(row-1, col).
Per ogni row da 0 a numRows-1, raccogli entry(row, col) per ogni col da 0 a row.
Restituisci l'elenco delle righe.

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

Costruisci ogni riga a partire da quella sopra

Intuizione

La versione ricorsiva continua a richiedere elementi delle righe precedenti, che comunque stai già costruendo. Calcola quindi le righe in ordine, dall’alto verso il basso, e quando riempi la riga r, leggi i valori che ti servono direttamente dalla riga r-1, che è già pronta. Ogni elemento richiede quindi una sola addizione. Questa è la programmazione dinamica nella sua forma più semplice: la tabella delle risposte più piccole è l’output stesso.

Inizia la riga r con r + 1 elementi pari a 1, così imposti entrambi i bordi. Poi, per ogni posizione interna c da 1 a r-1, impostala a above[c-1] + above[c]. Le righe 0 e 1 non hanno posizioni interne, quindi restano [1] e [1, 1] senza bisogno di un caso speciale.

Il triangolo contiene 1 + 2 + ... + n, cioè circa n²/2, elementi, e ciascuno richiede un tempo costante, quindi il lavoro è O(n²). A parte l’output, che devi comunque restituire, il metodo non richiede memoria aggiuntiva. Per numRows = 30 sono 465 elementi invece di due miliardi di chiamate.

Algoritmo

Inizia con un elenco vuoto di righe.
Per ogni row da 0 a numRows-1, crea row + 1 uni.
Per ogni col da 1 a row-1, impostalo sulla somma delle posizioni col-1 e col della riga precedente.
Aggiungi la riga e continua. Restituisci l’elenco.

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

Trappole e casi limite

I cicli sono brevi, quindi gli errori riguardano i limiti e le prime righe.

Restituire numRows + 1 righe. Se numeri le righe a partire da 0, l'ultima riga che ti serve è la riga numRows-1.
Eseguire il ciclo interno sugli estremi. La posizione 0 non ha un genitore a sinistra e la posizione row non ha un genitore a destra, quindi leggere above[col-1] o above[col] in quelle posizioni supera i limiti. Riempi solo le posizioni da 1 a row-1.
Scrivere un intervallo che non funziona per le righe piccole. L'intervallo Swift 1..<row va in errore quando row è 0, e l'intervallo R 2:(row-1) conta all'indietro fino a 1 quando row è 2. Proteggili con una condizione oppure inizializza le posizioni interne a 1, così le righe 0 e 1 non richiedono un ciclo.
Calcolare le voci usando i fattoriali. C(29, 14) rientra in un intero, ma 29! va in overflow anche con un intero a 64 bit, quindi una formula basata sui fattoriali stampa numeri errati nelle righe inferiori.
Riutilizzare lo stesso array per ogni riga. Se aggiungi ogni volta lo stesso array e poi lo modifichi, tutte le righe della risposta finiscono per essere uguali all'ultima.

Domande frequenti4

Qual è la complessità temporale della generazione del triangolo di Pascal?

Costruire ogni riga a partire da quella sopra richiede un tempo pari a O(n²) per n righe, perché il triangolo contiene circa n²/2 elementi e ciascuno richiede una sola addizione. È ottimale, perché devi scrivere ogni elemento dell'output. A parte l'output, usa O(1) spazio aggiuntivo.

Qual è la relazione tra il triangolo di Pascal e i coefficienti binomiali?

La voce k della riga r, contando entrambe da 0, è il coefficiente binomiale C(r, k), il numero di modi per scegliere k elementi tra r. La regola secondo cui ogni voce è la somma delle due soprastanti è l’identità C(r, k) = C(r-1, k-1) + C(r-1, k). È anche per questo che la somma degli elementi della riga r è 2^r.

Riesci a calcolare una riga senza costruire le righe che la precedono?

Sì. Inizia con 1 e ricava ogni voce successiva da quella precedente: C(r, k) = C(r, k-1) × (r-k+1) / k. Moltiplica prima di dividere, così la divisione è esatta, e usa un intero a 64 bit per il prodotto. La riga r richiede quindi O(r) di tempo e nessun’altra riga.

Perché il triangolo di Pascal è un problema di programmazione dinamica?

Ogni voce dipende da due sottoproblemi più piccoli, le voci che la precedono, e questi sottoproblemi si sovrappongono ampiamente: la ricorsione semplice li ricalcola continuamente. Costruire le righe in ordine memorizza ogni sottoproblema una sola volta e lo riutilizza, trasformando un lavoro esponenziale in O(n²).

Python

def generate(numRows):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Input

numRows = 5

Atteso

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