Climbing Stairs

Climbing stairs adalah contoh DP paling minimalis: ada n anak tangga, kita boleh naik 1 atau 2 langkah sekaligus, berapa cara untuk sampai ke puncak? Meski sederhana, masalah ini mengandung semua elemen inti DP — state, base case, recurrence, dan optimasi ruang. Masalah ini juga mengajarkan pola “jumlah cara” (counting) yang berbeda dari “nilai maksimum” (optimization). Pada Chapter ini kita akan membedah climbing stairs, ekstensi ke langkah variabel, dan variasi dengan batasan tambahan.

Aturan: Dari Mana Kita Datang? #

Pada climbing stairs, pertanyaan kuncinya bukan “ke mana kita pergi?” tetapi “dari mana kita datang?”. Untuk sampai ke tangga i, kita pasti datang dari i-1 (1 langkah) atau i-2 (2 langkah). Maka jumlah cara untuk sampai i = jumlah cara sampai i-1 + jumlah cara sampai i-2.

Mekanisme: Recurrence Fibonacci Offset #

Recurrence: dp[i] = dp[i-1] + dp[i-2] untuk i >= 2, dengan base case dp[0] = 1 (satu cara: tidak melompat) dan dp[1] = 1. Hasilnya persis Fibonacci dengan offset satu:

i	0	1	2	3	4	5	6
dp[i]	1	1	2	3	5	8	13

flowchart LR D0[dp 0 = 1] --> D2[dp 2 = 2] D1[dp 1 = 1] --> D2 D1 --> D3[dp 3 = 3] D2 --> D3 D2 --> D4[dp 4 = 5] D3 --> D4

Kode: Climbing Stairs Dasar #

cpp
#include <iostream>
#include <vector>

long long climb(int n) {
    if (n <= 1) return 1;
    std::vector<long long> dp(n + 1);
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

int main() {
    for (int n : {1, 2, 5, 10, 20, 30}) {
        std::cout << "climb(" << n << ") = " << climb(n) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
climb(1) = 1
climb(2) = 2
climb(5) = 8
climb(10) = 89
climb(20) = 10946
climb(30) = 1346269

Baris dp[0] = 1;: base case — ada tepat satu cara untuk berada di tanah (tidak melompat). Ini sedikit kontra-intuitif tetapi esensial agar recurrence bekerja.
Baris dp[1] = 1;: satu cara untuk naik satu tangga (1 langkah).
Baris dp[i] = dp[i - 1] + dp[i - 2];: jumlah cara = jumlah cara sampai i-1 (lalu 1 langkah) + jumlah cara sampai i-2 (lalu 2 langkah). Setiap cara sampai i-1 unik dari cara sampai i-2, sehingga tidak ada double counting.
Hasil climb(5) = 8: 8 cara untuk naik 5 tangga. Konfirmasi manual: 1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 1+2+2, 2+1+2, 2+2+1 → 8.

Ekstensi 1: Langkah Variabel #

Bagaimana bila kita boleh naik 1, 2, atau 3 langkah sekaligus? Recurrence menjadi:

text

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

Base case: dp[0]=1, dp[1]=1, dp[2]=2. Sekarang ini Tribonacci.

cpp
#include <iostream>
#include <vector>

long long climb_3(int n) {
    if (n < 0) return 0;
    if (n == 0) return 1;
    std::vector<long long> dp(n + 1);
    dp[0] = 1;
    for (int i = 1; i <= n; ++i) {
        dp[i] = dp[i - 1];
        if (i >= 2) dp[i] += dp[i - 2];
        if (i >= 3) dp[i] += dp[i - 3];
    }
    return dp[n];
}

int main() {
    for (int n : {3, 5, 10, 15}) {
        std::cout << "climb_3(" << n << ") = " << climb_3(n) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
climb_3(3) = 4
climb_3(5) = 13
climb_3(10) = 274
climb_3(15) = 5768

Baris dp[i] = dp[i - 1];: mulai dengan kontribusi dari i-1.
Baris if (i >= 2) dp[i] += dp[i - 2];: tambahkan kontribusi dari i-2 hanya jika valid (indeks non-negatif).
Baris if (i >= 3) dp[i] += dp[i - 3];: tambahkan kontribusi dari i-3.
Generalisasi: untuk himpunan langkah S = {s1, s2, ...}, dp[i] = sum(dp[i-s] for s in S if i-s >= 0).

Ekstensi 2: Langkah dengan Biaya Minimum #

Variasi populer: setiap tangga memiliki biaya cost[i], kita boleh mulai dari tangga 0 atau 1, dan sekali di tangga i kita membayar cost[i] untuk melompat ke i+1 atau i+2. Berapa biaya minimum untuk sampai ke puncak (di luar array)?

cpp
#include <iostream>
#include <vector>
#include <algorithm>

int min_cost_climb(const std::vector<int>& cost) {
    int n = static_cast<int>(cost.size());
    if (n == 0) return 0;
    if (n == 1) return cost[0];
    // dp[i] = biaya minimum untuk mencapai puncak mulai dari tangga i
    std::vector<int> dp(n + 1);
    dp[n] = 0;        // di puncak: tidak ada biaya lagi
    dp[n - 1] = cost[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        dp[i] = cost[i] + std::min(dp[i + 1], dp[i + 2]);
    }
    // Bisa mulai dari tangga 0 atau 1
    return std::min(dp[0], dp[1]);
}

int main() {
    std::vector<int> cost = {10, 15, 20};
    std::cout << "Biaya minimum = " << min_cost_climb(cost) << '\n';
    std::vector<int> cost2 = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
    std::cout << "Biaya minimum = " << min_cost_climb(cost2) << '\n';
    return 0;
}

Output yang Dihasilkan:

text

Biaya minimum = 15
Biaya minimum = 6

Baris dp[n] = 0;: base case — di puncak (di luar array), tidak ada biaya tersisa.
Baris dp[n - 1] = cost[n - 1];: dari tangga terakhir, hanya pilihan melompat 1 langkah. Bayar cost[n-1].
Baris dp[i] = cost[i] + std::min(dp[i + 1], dp[i + 2]);: dari tangga i, bayar cost[i] lalu pilih lompatan yang memberi biaya minimum total.
Baris return std::min(dp[0], dp[1]);: karena boleh mulai dari tangga 0 atau 1, ambil minimum.
Hasil pertama 15: mulai dari tangga 1 (biaya 15), lalu langsung lompat 2 ke puncak. Total 15.
Hasil kedua 6: lintasan optimal menghindari koin bernilai 100.

Optimasi Ruang: Sliding Window #

Karena dp[i] hanya bergantung pada dp[i-1] dan dp[i-2], kita bisa menyimpan dua variabel:

cpp
#include <iostream>

long long climb_opt(int n) {
    if (n <= 1) return 1;
    long long prev2 = 1, prev1 = 1;
    for (int i = 2; i <= n; ++i) {
        long long cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

int main() {
    for (int n : {10, 50, 80}) {
        std::cout << "climb_opt(" << n << ") = " << climb_opt(n) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
climb_opt(10) = 89
climb_opt(50) = 20365011074
climb_opt(80) = 37889062373143906

Variabel prev2, prev1: menyimpan dp[i-2] dan dp[i-1].
Update per iterasi: cur = prev1 + prev2, lalu geser jendela.
Kompleksitas: O(n) waktu, O(1) ruang. Optimal.

Aplikasi Pola Serupa #

Pola “jumlah cara untuk sampai ke state” muncul di banyak masalah DP:

Coin change (count ways): jumlah cara untuk membentuk nilai tertentu.
Dice combinations: jumlah cara mendapat total n dari lemparan dadu.
Decode ways: jumlah cara men-decode string digit.
Unique paths: jumlah cara untuk berjalan dari sudut kiri-atas ke kanan-bawah pada grid.

Semua mengikuti pola yang sama: identifikasi pilihan transisi, base case, dan recurrence penjumlahan.

Ringkasan #

Climbing stairs: dp[i] = dp[i-1] + dp[i-2]. Pola “jumlah cara” (counting).
Base case dp[0]=1 esensial — satu cara untuk “di posisi awal”.
Ekstensi ke langkah variabel: dp[i] = sum(dp[i-s] for s in steps).
Variasi biaya minimum: transisi min alih-alih +.
Sliding window berlaku untuk semua recurrence linier dengan k kecil.