Climbing Stairs

Q: Perché salire le scale è un problema di Fibonacci?

Ogni salita fino al gradino n termina con un passo di 1 da n-1 oppure con un passo di 2 da n-2 , quindi ways(n) = ways(n-1) + ways(n-2) . Questa è la regola di Fibonacci. Con ways(1) = 1 e ways(2) = 2 , i conteggi sono 1, 2, 3, 5, 8, 13, ovvero la sequenza di Fibonacci spostata di una posizione: ways(n) = F(n+1) .

Q: Qual è la complessità temporale del problema delle scale?

Il ciclo bottom up esegue n-2 addizioni, quindi impiega un tempo O(n) e uno spazio aggiuntivo O(1) . La ricorsione semplice è esponenziale: il numero di chiamate cresce di un fattore di circa 1.618 a ogni passaggio e raggiunge 2269806339, circa 2.3 × 10^9 , con n = 45 . La memoizzazione riduce la ricorsione a un tempo O(n) e uno spazio O(n) .

Q: Come si risolve il problema delle scale con passi di 1, 2 o 3?

Dividi di nuovo le scalate in base alla loro ultima mossa: ways(n) = ways(n-1) + ways(n-2) + ways(n-3) . Parti da ways(0) = 1 (la scalata vuota), ways(1) = 1 e ways(2) = 2 , e conserva gli ultimi tre conteggi invece di due. Il tempo resta O(n) e lo spazio O(1) .

FacileProgrammazione dinamica Ricorsione

+10

Ti trovi in fondo a una scala con n gradini. Ogni mossa fa salire di 1 o 2 gradini. Due salite contano come diverse quando le loro sequenze di mosse differiscono, quindi 1, 2 e 2, 1 sono due modi. La tua funzione riceve n e restituisce il numero di modi distinti per raggiungere la cima.

Funzione

climbStairs(n: integer) → integer

ninteger: il numero di gradini della scalinata
Restituisceinteger: il numero di sequenze distinte di passi da 1 e da 2 che raggiungono il passo n

Vincoli

1 ≤ n ≤ 45
La risposta rientra in un intero con segno a 32 bit: n = 45 dà 1836311903.

Esempi

Input: n = 3
Output: 3
Spiegazione: Si possono salire tre gradini come 1, 1, 1, come 1, 2 o come 2, 1, quindi ci sono 3 modi.

Input: n = 5
Output: 8
Spiegazione: Ogni salita al gradino 5 termina con un passo singolo dal gradino 4 (5 modi per arrivarci) oppure con un passo doppio dal gradino 3 (3 modi), quindi la risposta è 5 + 3 = 8.

+13 test nascosti all’invio

Per approfondire

Che cosa succede se alcuni gradini sono rotti e potresti non riuscire mai a salirci? Come cambia la ricorrenza e qual è il conteggio per un gradino rotto?

Suggerimenti

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

0 di 3 aperti

Soluzione

Elencare ogni salita non funziona: una scala di 45 gradini ne ha 1836311903. Il punto di partenza è l’ultima mossa. Ogni salita fino al gradino n passa dal gradino n-1 o dal gradino n-2 subito prima della fine, da cui si ottiene ways(n) = ways(n-1) + ways(n-2), la ricorrenza di Fibonacci. Calcolala dal basso verso l’alto e ti bastano due variabili.

Ricorsione semplice sull'ultima mossa

Corretto, ma non termina sui test più grandi

Intuizione

Dividi le salite per raggiungere il gradino n in base all’ultima mossa. Una salita che termina con un passo di 1 gradino si trovava sul gradino n-1 prima di farlo, e ci sono ways(n-1) salite di questo tipo. Una salita che termina con un passo di 2 gradini si trovava sul gradino n-2, e ce ne sono ways(n-2). Ogni salita termina in un modo o nell’altro e nessuna termina in entrambi i modi, quindi ways(n) = ways(n-1) + ways(n-2).

La ricorsione richiede due casi base. Un gradino ha una salita e due gradini ne hanno due (1, 1 e 2). In entrambi i casi la risposta è uguale a n, quindi la funzione restituisce n quando n ≤ 2 e la somma altrimenti.

La risposta è corretta, ma il lavoro aumenta a dismisura. climbStairs(5) richiede il gradino 3 due volte e il gradino 2 tre volte, per un totale di 9 chiamate, e il numero di chiamate cresce come le risposte stesse. Per n = 45 la funzione effettua 2269806339 chiamate, circa 2.3 × 10^9, troppe per un limite di tempo. La ricorsione è profonda solo n livelli, quindi lo stack usa spazio O(n).

Algoritmo

Se n ≤ 2, restituisci n.
Conta le salite che raggiungono il gradino n-1 con una chiamata ricorsiva.
Conta le salite che raggiungono il gradino n-2 con una seconda chiamata ricorsiva.
Restituisci la somma dei due conteggi.

def climbStairs(n):
    if n <= 2:
        return n  # 1 step: one way, 2 steps: two ways
    return climbStairs(n - 1) + climbStairs(n - 2)

Ricorsione con una memoria

Intuizione

La ricorsione è lenta solo perché dimentica. Ogni conteggio dipende solo da k, quindi, una volta che conosci il conteggio per il passo k, non cambia mai. Tieni una memo, un array con uno slot per ogni passo, e scrivi ogni conteggio lì la prima volta che lo calcoli. Ogni richiesta successiva dello stesso passo legge lo slot invece di ricorrere di nuovo.

Ora ciascuno dei conteggi dal passo 3 al passo n viene calcolato una sola volta, con una somma. Per n = 5, le chiamate scendono fino al passo 2 una volta, poi le risposte risalgono come 3, 5 e 8, e la seconda richiesta per il passo 3 è una ricerca. Questo richiede tempo O(n) invece di miliardi di chiamate.

La memo contiene n + 1 numeri e la ricorsione ha ancora una profondità di n livelli, quindi lo spazio è O(n). Uno 0 in uno slot significa che il valore non è ancora noto, il che è sicuro perché ogni conteggio reale è almeno 1.

Algoritmo

Crea una memoria con n + 1 slot, tutti a 0.
Nella funzione helper ricorsiva, restituisci k quando k ≤ 2.
Se lo slot della memoria per k è 0, riempilo con la somma dei risultati della funzione helper per k-1 e k-2.
Restituisci lo slot della memoria.
Chiama la funzione helper su n.

def climbStairs(n):
    memo = [0] * (n + 1)  # memo[k] = ways to reach step k, 0 = not known yet

    def ways(k):
        if k <= 2:
            return k
        if memo[k] == 0:
            memo[k] = ways(k - 1) + ways(k - 2)
        return memo[k]

    return ways(n)

Dal basso verso l’alto con due variabili

Intuizione

Inverti la ricorsione. Invece di partire dall’alto e procedere verso il basso, parti dal basso e costruisci verso l’alto. Quando calcoli il conteggio per il passo k, i conteggi per k-1 e k-2 sono già noti e non si legge mai più nessun valore precedente. Quindi due variabili sostituiscono l’intera memorizzazione.

Fai in modo che prev contenga il conteggio per il passo k-2 e che curr contenga quello per il passo k-1. Inizia con prev = 1 e curr = 2, i conteggi per i passi 1 e 2. A ogni passo sommali in next, poi fai avanzare la coppia. Per n = 5 la coppia passa da (1, 2) a (2, 3), (3, 5) e (5, 8), e curr = 8 è la risposta.

Il ciclo viene eseguito n-2 volte con una somma ciascuna, richiede un tempo O(n) e mantiene tre interi, occupando uno spazio O(1). Calcola next prima di sovrascrivere prev, altrimenti la somma userà il valore sbagliato.

Algoritmo

Se n ≤ 2, restituisci n.
Imposta prev = 1 e curr = 2.
Per k da 3 a n, calcola next = prev + curr, poi imposta prev = curr e curr = next.
Restituisci curr.

def climbStairs(n):
    if n <= 2:
        return n
    prev, curr = 1, 2  # ways to reach steps 1 and 2
    for _ in range(n - 2):
        prev, curr = curr, prev + curr
    return curr

Trappole e casi limite

La ricorrenza è breve, quindi la maggior parte dei bug si trova nei casi base, nel tempo di esecuzione e nel limite a 32 bit.

Consegnare la versione con la ricorsione semplice. Supera i test piccoli, ma poi richiede circa 2.3 × 10^9 chiamate per n = 45. Memorizza ogni conteggio una sola volta.
Casi base errati. Due gradini possono essere saliti in due modi: 1, 1 e 2. Restituire 1 per n = 2 sposta tutte le risposte successive: otterresti 2 per n = 3 invece di 3.
Contare le scelte invece delle sequenze. 1, 2 e 2, 1 sono due modi di salire. Contare solo quanti passi da 2 fai dà n/2 + 1, che per n = 5 è 3 invece di 8.
Riempire una tabella senza un controllo preliminare. Con n = 1, una tabella di n + 1 = 2 slot non ha spazio per il conteggio del gradino 2. Restituisci subito n quando n ≤ 2.
Procedere di un passo di troppo. Il conteggio per 45 gradini, 1836311903, entra in 32 bit, ma quello per 46 gradini è 2971215073 e non ci entra. Un ciclo che calcola un valore in più va in overflow e produce un numero negativo in Java, C o C#.

Domande frequenti4

Perché salire le scale è un problema di Fibonacci?

Ogni salita fino al gradino n termina con un passo di 1 da n-1 oppure con un passo di 2 da n-2, quindi ways(n) = ways(n-1) + ways(n-2). Questa è la regola di Fibonacci. Con ways(1) = 1 e ways(2) = 2, i conteggi sono 1, 2, 3, 5, 8, 13, ovvero la sequenza di Fibonacci spostata di una posizione: ways(n) = F(n+1).

Qual è la complessità temporale del problema delle scale?

Il ciclo bottom up esegue n-2 addizioni, quindi impiega un tempo O(n) e uno spazio aggiuntivo O(1). La ricorsione semplice è esponenziale: il numero di chiamate cresce di un fattore di circa 1.618 a ogni passaggio e raggiunge 2269806339, circa 2.3 × 10^9, con n = 45. La memoizzazione riduce la ricorsione a un tempo O(n) e uno spazio O(n).

Qual è la differenza tra la memoizzazione e la soluzione bottom-up?

La memoizzazione mantiene la funzione ricorsiva e memorizza nella cache ogni risultato la prima volta che viene calcolato, quindi procede dall’alto verso il basso e ha bisogno dello stack delle chiamate e di una tabella. Il ciclo dal basso verso l’alto calcola i conteggi in ordine crescente, quindi ogni valore di cui ha bisogno è già noto e non comporta ricorsione. Entrambi richiedono O(n) operazioni. Il ciclo permette anche di eliminare la tabella e mantenere due numeri.

Come si risolve il problema delle scale con passi di 1, 2 o 3?

Dividi di nuovo le scalate in base alla loro ultima mossa: ways(n) = ways(n-1) + ways(n-2) + ways(n-3). Parti da ways(0) = 1 (la scalata vuota), ways(1) = 1 e ways(2) = 2, e conserva gli ultimi tre conteggi invece di due. Il tempo resta O(n) e lo spazio O(1).

Python

def climbStairs(n):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Input

n = 3

Atteso

Climbing Stairs

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Ricorsione semplice sull'ultima mossa

Ricorsione con una memoria

Dal basso verso l’alto con due variabili

Trappole e casi limite

Domande frequenti4

Problemi simili