Coding Interview Prep · Pelajaran

Menaiki Tangga & Kombinasi Koin

Rekurensi 1D klasik dari awal

Pelajaran 3 dari 413 langkah

Menaiki Tangga & Kombinasi Koin adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Berkenalan dengan Tangga

Anda dapat melangkah 1 atau 2 anak tangga sekaligus. Berapa banyak cara untuk mencapai anak tangga n? DP 1D klasik ini sebenarnya adalah Fibonacci yang disamarkan.

Temukan Rekurensinya

Untuk berdiri di anak tangga i, Anda datang dari i-1 atau i-2. Jadi, dp[i] = dp[i-1] + dp[i-2], dengan menjumlahkan kedua langkah terakhir.

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

Tetapkan Kasus Dasar

Ada satu cara untuk tetap berada di lantai dasar dan satu cara untuk mencapai anak tangga 1. Kasus dasar tersebut menjadi awal bagi seluruh tabel.

dp[0], dp[1] = 1, 1

Isi dan Baca Jawabannya

Lakukan perulangan ke arah atas, dan sel terakhir akan menyimpan jumlahnya. Seluruh solusi ini hanyalah perulangan tabulasi yang sangat singkat.

for i in range(2, n+1):
    dp[i] = dp[i-1] + dp[i-2]

Sederhanakan Menjadi Dua Variabel

Anda hanya memerlukan dua nilai terakhir, jadi hapus lariknya. Versi dengan ruang O(1) ini menjadi favorit dalam kompetisi.

a, b = 1, 1
for _ in range(n):
    a, b = b, a+b

Beralih ke Kombinasi Koin

Diberikan nilai-nilai koin, hitung banyak cara untuk membentuk jumlah A. Urutan tidak berpengaruh di sini, jadi kita menghitung kombinasi, bukan urutan.

coins = [1, 2, 5]

Tabel Kombinasi

Misalkan dp[x] adalah banyaknya cara untuk membentuk x. Mulailah dengan satu cara untuk membentuk nol: himpunan koin kosong.

dp = [0]*(A+1)
dp[0] = 1

Letakkan Perulangan Koin di Luar

Letakkan perulangan koin di luar perulangan jumlah. Urutan ini menghitung setiap kombinasi tepat satu kali, bukan permutasinya.

for c in coins:
    for x in range(c, A+1):
        dp[x] += dp[x-c]

Kombinasi vs Permutasi

Tukar urutan perulangannya, dan Anda akan menghitung cara yang berurutan. Susunan perulangan saja dapat mengubah makna jawaban.

Varian Minimum Penukaran Koin

Untuk mendapatkan jumlah koin paling sedikit, simpan nilai minimum, bukan jumlah. Inisialisasi dengan tak terhingga, lalu ambil 1 ditambah submasalah terbaik.

dp[x] = min(dp[x], dp[x-c] + 1)

Satu Pola, Banyak Bentuk

Tangga dan koin memiliki pola yang sama: setiap keadaan menjumlahkan atau meminimalkan beberapa keadaan sebelumnya. Kenali pola tersebut, dan kodenya akan tersusun dengan sendirinya.

Pemeriksaan Cepat

Saat menghitung kombinasi koin, urutan perulangan mana yang menghindari duplikasi?

Jawab di pelajaran interaktif

Rangkuman: Jumlahkan Langkah Terakhir

Sekarang Anda dapat menyelesaikan masalah tangga dan penghitungan koin dengan rekurensi 1D. Setiap jawaban menjumlahkan beberapa keadaan sebelumnya, dan urutan perulangan menentukan kombinasi atau permutasi.

Gratis untuk memulai

Belajar Coding Interview Prep dengan tutor AI — gratis

Tulis dan jalankan kode asli di browser kamu, dapatkan bantuan instan dari tutor AI 24/7, dan lanjutkan di mana kamu tinggalkan di web atau aplikasi.

Kursus: 90
Pelajaran: 360

Mulai belajar gratis Lihat kursus lengkapnya

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Menaiki Tangga & Kombinasi Koin” gratis?

Ya — teks lengkap “Menaiki Tangga & Kombinasi Koin” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Menaiki Tangga & Kombinasi Koin”?

Rekurensi 1D klasik dari awal Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?

Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.

Berapa lama pelajaran “Menaiki Tangga & Kombinasi Koin” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?

Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

← Kembali ke Coding Interview Prep