Unique Paths

Q: Qual è la formula per i percorsi unici?

La risposta è il coefficiente binomiale C(m+n-2, m-1) . Ogni percorso compie m-1 mosse verso il basso e n-1 mosse verso destra, in un certo ordine; scegliere quali delle m+n-2 mosse sono verso il basso determina il percorso. Per una griglia 3 × 4, C(5, 2) = 10.

MedioProgrammazione dinamica Matematica e simulazione

+10

Un robot parte dalla cella in alto a sinistra di una griglia con m righe e n colonne e deve raggiungere la cella in basso a destra. Ogni mossa lo sposta di una cella a destra o di una cella in basso. Restituisci il numero di percorsi diversi che può seguire.

Funzione

uniquePaths(m: integer, n: integer) → integer

minteger: il numero di righe nella griglia
ninteger: il numero di colonne nella griglia
Restituisceinteger: il numero di percorsi diversi dalla cella in alto a sinistra alla cella in basso a destra

Vincoli

1 ≤ m, n ≤ 100
La risposta è al massimo 2 × 10⁹, quindi rientra in un intero con segno a 32 bit.

Esempi

Input: m = 3n = 4
Output: 10
Spiegazione: Ogni percorso fa 2 mosse verso il basso e 3 verso destra, 5 mosse in tutto. Un percorso è determinato da quali 2 delle 5 mosse vanno verso il basso, e ci sono 10 modi per sceglierle.

+14 test nascosti all’invio

Per approfondire

Per una griglia di 100 × 100, la risposta ha 59 cifre. Come la restituiresti modulo 10^9+7 usando la formula, quando dividere per i non funziona più?

Suggerimenti

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

0 di 3 aperti

Soluzione

Elencare i percorsi uno per uno è impossibile: una griglia 17 × 17 ne ha già 601.080.390. Devi contarli senza elencarli. I percorsi che arrivano a una cella sono i percorsi che arrivano alla cella sopra più quelli che arrivano alla cella alla sua sinistra: così la griglia diventa una tabella da riempire in un unico passaggio. Un percorso è anche semplicemente un ordine di spostamenti verso il basso e verso destra, e questo ci dà una formula chiusa.

Conta ogni percorso con la ricorsione

Corretto, ma non termina sui test più grandi

Intuizione

Considera l’ultima mossa del robot nella cella in basso a destra. È arrivato o scendendo dalla cella sopra o andando a destra dalla cella a sinistra, mai in entrambi i modi. Quindi i percorsi attraverso una griglia m × n sono i percorsi attraverso la griglia con una riga in meno, uniquePaths(m-1, n), più i percorsi attraverso la griglia con una colonna in meno, uniquePaths(m, n-1).

La ricorsione si ferma con una griglia con una riga o una colonna, dove il robot può solo andare dritto, quindi c’è esattamente 1 percorso. Ogni percorso termina con una delle due mosse, quindi ogni percorso viene contato una volta e il totale è corretto.

È lento perché ogni percorso termina in un caso base che restituisce 1, quindi il numero di chiamate è almeno pari alla risposta stessa. Una griglia di 17 × 17 richiede più di 600 milioni di chiamate e i test arrivano a risposte vicine a 1.6 × 10^9. Le stesse griglie più piccole vengono calcolate molte volte: (m-1, n-1) viene raggiunto una volta da ciascuno dei suoi due genitori, e le ripetizioni si moltiplicano man mano che si procede verso il basso.

Algoritmo

Se m o n è 1, restituisci 1: l'unico percorso è una linea retta.
Altrimenti, conta i percorsi la cui ultima mossa va verso il basso, uniquePaths(m-1, n).
Conta i percorsi la cui ultima mossa va verso destra, uniquePaths(m, n-1).
Restituisci la loro somma.

def uniquePaths(m, n):
    # One row or one column: the only path is a straight line
    if m == 1 or n == 1:
        return 1
    # The last move came down from the row above or right from the column before
    return uniquePaths(m - 1, n) + uniquePaths(m, n - 1)

Riempi la griglia una riga alla volta

Intuizione

La ricorsione interroga le stesse celle ancora e ancora, e ci sono solo m × n celle. Conta una sola volta i percorsi che arrivano a ciascuna cella, in un ordine che garantisca che le celle necessarie siano sempre pronte.

Stato: paths[r][c] è il numero di percorsi dalla cella in alto a sinistra alla riga r, colonna c. Relazione di ricorrenza: paths[r][c] = paths[r-1][c] + paths[r][c-1], i percorsi che arrivano dall’alto più quelli che arrivano da sinistra. Casi base: ogni cella della riga superiore e della colonna di sinistra ha 1 percorso, una linea retta. Ordine: riga per riga, da sinistra a destra, così la cella sopra e quella a sinistra vengono riempite prima che servano.

Per m = 3 e n = 4 le righe sono 1 1 1 1, poi 1 2 3 4, poi 1 3 6 10, e la risposta è l’ultima cella, 10.

Ora osserva cosa legge il riempimento: solo la riga sopra e la riga che stai riempiendo. Quindi conserva una sola riga. Prima di aggiornare row[c], contiene ancora il conteggio della riga sopra, mentre row[c-1] contiene già il nuovo conteggio alla sua sinistra, quindi row[c] += row[c-1] è tutta la relazione di ricorrenza. Il tempo resta O(m × n) e la memoria scende da O(m × n) a O(n).

Algoritmo

Crea row con n elementi, tutti pari a 1: la riga superiore.
Ripeti m-1 volte, una per ogni riga sotto quella superiore.
In ogni riga, per c da 1 a n-1, aggiungi row[c-1] a row[c]. row[0] rimane 1: è la colonna di sinistra.
Restituisci row[n-1].

def uniquePaths(m, n):
    # row[c] counts the paths into column c of the current row.
    # The top row is all 1s: the only way along it is straight right.
    row = [1] * n
    for _ in range(m - 1):
        for c in range(1, n):
            # Paths from above (the old row[c]) plus paths from the left (the new row[c-1])
            row[c] += row[c - 1]
    return row[n - 1]

Conta le mosse con un coefficiente binomiale

Intuizione

Ogni percorso compie esattamente m-1 mosse verso il basso e n-1 mosse verso destra, per un totale di m+n-2 mosse, in un certo ordine. Ogni ordine è un percorso valido: il robot non compie mai più di m-1 mosse verso il basso o n-1 mosse verso destra, quindi non esce mai dalla griglia. Un percorso equivale quindi a scegliere quali m-1 delle m+n-2 mosse compiere verso il basso, e la risposta è il coefficiente binomiale C(m+n-2, m-1).

La tabella dell'approccio precedente è il triangolo di Pascal girato su un lato, ed è per questo che i due risultati coincidono. Per calcolare il coefficiente senza fattoriali enormi, costruiscilo un fattore alla volta. Con N = m+n-2 e k = min(m, n)-1, moltiplica per N-k+i e poi dividi per i, per i da 1 a k. Dopo il passaggio i, il valore progressivo è C(N-k+i, i), un numero intero, quindi ogni divisione è esatta.

Per m = 3 e n = 4: N = 5, k = 2, e il valore diventa 1 × 4 / 1 = 4, poi 4 × 5 / 2 = 10. Scegliere il lato più corto mantiene il ciclo a 99 passaggi o meno. Il prodotto prima dell'ultima divisione è k volte la risposta. Per una griglia 17 × 17, sono 16 × 601,080,390, circa 9.6 × 10^9, oltre l'intervallo a 32 bit, quindi mantienilo in un intero a 64 bit.

Algoritmo

Imposta N = m+n-2, il numero di mosse, e k = min(m, n)-1.
Inizializza un conteggio a 64 bit a 1.
Per i da 1 a k, moltiplica il conteggio per N-k+i, poi dividilo per i.
Restituisci il conteggio.

def uniquePaths(m, n):
    # A path is m+n-2 moves; count the ways to choose which of them go down.
    # Choose along the shorter side so the loop stays short.
    moves = m + n - 2
    k = min(m, n) - 1
    count = 1
    for i in range(1, k + 1):
        # count goes from C(moves-k+i-1, i-1) to C(moves-k+i, i); the division is exact
        count = count * (moves - k + i) // i
    return count

Trappole e casi limite

Il conteggio è breve, quindi i bug si nascondono ai bordi della griglia e nelle dimensioni dei numeri.

Calcolare (m+n-2)! e dividere per gli altri due fattoriali causa un overflow molto prima che lo faccia la risposta: 21! supera già l'intervallo a 64 bit e m+n-2 arriva a 105 in una griglia 100 × 7.
Dividere prima di moltiplicare, come in count / i * (N-k+i), tronca il risultato, perché count non è sempre un multiplo di i. Moltiplica prima: il prodotto è sempre divisibile esattamente.
Il prodotto count × (N-k+i) può superare 2^31 anche quando la risposta non lo supera. Conservalo in un intero a 64 bit.
Lasciare la riga superiore o la colonna sinistra a 0 invece che a 1 fa sì che ogni cella sia 0. Una griglia con una sola riga o una sola colonna ha esattamente 1 percorso.
Scambiare righe e colonne non cambia la risposta, poiché C(m+n-2, m-1) = C(m+n-2, n-1).

Domande frequenti4

Qual è la formula per i percorsi unici?

La risposta è il coefficiente binomiale C(m+n-2, m-1). Ogni percorso compie m-1 mosse verso il basso e n-1 mosse verso destra, in un certo ordine; scegliere quali delle m+n-2 mosse sono verso il basso determina il percorso. Per una griglia 3 × 4, C(5, 2) = 10.

Qual è la complessità temporale di Unique Paths?

La tabella di programmazione dinamica richiede un tempo O(m × n) e uno spazio O(n) se mantieni una sola riga. La formula binomiale richiede un tempo O(min(m, n)) e uno spazio O(1). La ricorsione semplice effettua almeno tante chiamate quanti sono i percorsi, un numero esponenziale rispetto a m + n.

Come si risolve il problema dei percorsi unici quando alcune celle sono bloccate?

Usa la stessa tabella e imposta a 0 il conteggio di una cella bloccata, in modo che nessun percorso la attraversi. La riga superiore e la colonna sinistra non sono più tutte composte da 1: ogni cella dopo una cella bloccata nella riga superiore ha 0 percorsi. La formula non funziona più, perché presuppone che ogni ordine di mosse sia consentito.

Perché la tabella dei percorsi unici corrisponde al triangolo di Pascal?

Ogni cella somma la cella sopra e quella alla sua sinistra: questa è la regola che costruisce il triangolo di Pascal, letto lungo le sue diagonali. La cella alla riga r e alla colonna c contiene C(r+c, r), quindi la cella in basso a destra contiene C(m+n-2, m-1).

Python

def uniquePaths(m, n):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

m = 3
n = 4

Atteso

Unique Paths

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Conta ogni percorso con la ricorsione

Riempi la griglia una riga alla volta

Conta le mosse con un coefficiente binomiale

Trappole e casi limite

Domande frequenti4

Problemi simili