Climbing Stairs

Q: Mengapa Climbing Stairs merupakan masalah Fibonacci?

Setiap pendakian ke anak tangga n berakhir dengan langkah 1 dari n-1 atau langkah 2 dari n-2 , sesuai aturan Fibonacci. Dengan ways(1) = 1 dan ways(2) = 2 , jumlahnya menjadi 1, 2, 3, 5, 8, 13: barisan Fibonacci yang bergeser satu posisi, ways(n) = F(n+1) .

Q: Apa kompleksitas waktu dari Climbing Stairs?

Perulangan dari bawah ke atas melakukan n-2 penjumlahan: waktu O(n) dan ruang tambahan O(1) . Rekursi dengan memo membutuhkan waktu O(n) dan ruang O(n) . Rekursi biasa bersifat eksponensial, dengan jumlah pemanggilan yang bertambah sekitar 1.618 kali lipat di setiap langkah.

MudahDynamic programming Rekursi

+10

Kamu berada di dasar tangga dengan n anak tangga. Setiap langkah menaiki 1 atau 2 anak tangga. Dua cara menaiki tangga dianggap berbeda jika urutan langkahnya berbeda, jadi 1, 2 dan 2, 1 adalah dua cara. Fungsi kamu menerima n dan mengembalikan jumlah cara berbeda untuk mencapai puncak.

Fungsi

climbStairs(n: integer) → integer

ninteger: jumlah anak tangga
Mengembalikaninteger: jumlah urutan berbeda dari langkah 1 dan langkah 2 yang mencapai langkah ke-n

Batasan

1 ≤ n ≤ 45
Jawabannya muat dalam bilangan bulat bertanda 32-bit: n = 45 menghasilkan 1836311903.

Contoh

Input: n = 3
Output: 3
Penjelasan: Tiga anak tangga dapat dinaiki dengan urutan 1, 1, 1, 1, 2, atau 2, 1, jadi ada 3 cara.

Input: n = 5
Output: 8
Penjelasan: Setiap pendakian ke langkah 5 berakhir dengan langkah 1 dari langkah 4 (5 cara untuk sampai ke sana) atau langkah 2 dari langkah 3 (3 cara), jadi jawabannya adalah 5 + 3 = 8.

Pertanyaan lanjutan

Apa yang terjadi jika beberapa anak tangga rusak dan kamu mungkin tidak bisa menginjaknya? Bagaimana rekurensinya berubah, dan berapa jumlahnya untuk anak tangga yang rusak?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Mencantumkan setiap cara mendaki tidak akan berhasil: 45 langkah menghasilkan 1836311903 cara. Setiap cara mencapai langkah n berpijak di langkah n-1 atau langkah n-2 tepat sebelum gerakan terakhirnya, jadi ways(n) = ways(n-1) + ways(n-2), yaitu relasi rekurensi Fibonacci. Bangun dari bawah ke atas, dan kamu hanya memerlukan dua variabel.

Rekursi biasa pada langkah terakhir

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Pisahkan pendakian menuju anak tangga n berdasarkan langkah terakhirnya. Pendakian yang berakhir dengan langkah 1 berpijak di anak tangga n-1, sedangkan yang berakhir dengan langkah 2 berpijak di anak tangga n-2, dan tidak ada pendakian yang berakhir dengan kedua cara tersebut, jadi kedua jumlahnya dijumlahkan. Satu anak tangga memiliki satu pendakian dan dua anak tangga memiliki dua pendakian, jadi kembalikan n saat n ≤ 2.

Rekursi melupakan apa yang sudah dihitungnya. climbStairs(5) meminta anak tangga 3 dua kali dan anak tangga 2 tiga kali, total 9 pemanggilan, dan n = 45 memerlukan 2269806339 pemanggilan.

Algoritma

Jika n ≤ 2, kembalikan n.
Hitung jumlah cara mendaki yang mencapai anak tangga n-1 dengan pemanggilan rekursif.
Hitung jumlah cara mendaki yang mencapai anak tangga n-2 dengan pemanggilan rekursif kedua.
Kembalikan jumlah dari kedua hitungan tersebut.

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

Rekursi dengan memo

Intuisi

Jumlah untuk langkah k hanya bergantung pada k, jadi nilainya tidak pernah berubah setelah diketahui. Simpan jumlah tersebut di slot memo saat pertama kali kamu menghitungnya, lalu setiap permintaan berikutnya membaca slot itu alih-alih melakukan rekursi. Dengan begitu, setiap jumlah dari langkah 3 hingga langkah n dihitung sekali, dengan satu penjumlahan: waktu O(n). Untuk n = 5, permintaan kedua untuk langkah 3 adalah pencarian.

Nilai 0 di slot berarti belum diketahui, dan ini aman karena setiap jumlah sebenarnya setidaknya 1.

Algoritma

Buat memo dengan n + 1 slot, semuanya 0.
Di helper rekursif, kembalikan k jika k ≤ 2.
Jika slot memo untuk k bernilai 0, isi slot itu dengan hasil helper untuk k-1 dan k-2 yang dijumlahkan.
Kembalikan slot memo.
Panggil helper dengan 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)

Dari bawah ke atas dengan dua variabel

Intuisi

Bangunlah dari bawah ke atas. Saat kamu menghitung jumlah untuk langkah k, hanya jumlah untuk k-1 dan k-2 yang dibaca, dan tidak ada nilai yang lebih lama yang perlu digunakan lagi. Jadi, dua variabel menggantikan memo.

Untuk n = 5, pasangan (prev, curr) bergerak dari (1, 2) ke (2, 3), (3, 5), lalu (5, 8), dan curr = 8 adalah jawabannya. Hitung next sebelum kamu menimpa prev, atau jumlahnya akan menggunakan nilai yang salah.

Algoritma

Jika n ≤ 2, kembalikan n.
Tetapkan prev = 1 dan curr = 2.
Untuk k dari 3 hingga n, hitung next = prev + curr, lalu tetapkan prev = curr dan curr = next.
Kembalikan 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

Jebakan dan kasus tepi

Kasus dasar yang salah. Dua langkah memiliki dua cara naik, yaitu 1, 1 dan 2. Mengembalikan 1 untuk n = 2 menggeser semua jawaban berikutnya: kamu mendapatkan 2 untuk n = 3, bukan 3.
Menghitung pilihan, bukan urutan. Menghitung hanya berapa banyak langkah 2 yang kamu ambil menghasilkan n/2 + 1, yaitu 3 untuk n = 5, bukan 8.
Mengisi tabel tanpa pemeriksaan. Untuk n = 1, tabel dengan n + 1 = 2 slot tidak memiliki ruang untuk langkah 2. Kembalikan n terlebih dahulu jika n ≤ 2.
Menjalankan satu langkah terlalu jauh. Jumlah untuk 46 langkah adalah 2971215073, yang menyebabkan int 32-bit meluap menjadi angka negatif di Java, C, atau C#.

Pertanyaan yang sering diajukan3

Mengapa Climbing Stairs merupakan masalah Fibonacci?

Setiap pendakian ke anak tangga n berakhir dengan langkah 1 dari n-1 atau langkah 2 dari n-2, sesuai aturan Fibonacci. Dengan ways(1) = 1 dan ways(2) = 2, jumlahnya menjadi 1, 2, 3, 5, 8, 13: barisan Fibonacci yang bergeser satu posisi, ways(n) = F(n+1).

Apa kompleksitas waktu dari Climbing Stairs?

Perulangan dari bawah ke atas melakukan n-2 penjumlahan: waktu O(n) dan ruang tambahan O(1). Rekursi dengan memo membutuhkan waktu O(n) dan ruang O(n). Rekursi biasa bersifat eksponensial, dengan jumlah pemanggilan yang bertambah sekitar 1.618 kali lipat di setiap langkah.

Bagaimana cara menyelesaikan masalah Mendaki Tangga dengan langkah 1, 2, atau 3?

Pisahkan lagi cara menaiki tangga berdasarkan langkah terakhirnya: ways(n) = ways(n-1) + ways(n-2) + ways(n-3). Mulai dari ways(0) = 1 (menaiki tangga kosong), ways(1) = 1 dan ways(2) = 2, lalu simpan tiga hitungan terakhir, bukan dua. Waktunya tetap O(n) dan ruangnya O(1).

def climbStairs(n):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

n = 3

Output yang diharapkan

Climbing Stairs

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Rekursi biasa pada langkah terakhir

Rekursi dengan memo

Dari bawah ke atas dengan dua variabel

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa