House Robber: Rekurensi Ambil atau Lewati
Modelkan keputusan mengambil atau melewati sebagai relasi rekurensi DP, kurangi ruang menjadi dua variabel, lalu perluas solusi ke rumah-rumah melingkar.
House Robber: Rekurensi Ambil atau Lewati adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 1 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 DSA Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Masalah Perampok Rumah
Masalah Perampok Rumah menanyakan hal berikut: dengan sebuah larik bilangan bulat non-negatif yang mewakili jumlah uang di setiap rumah, temukan jumlah maksimum yang dapat Anda rampok tanpa merampok dua rumah yang bersebelahan. Sebagai contoh, [2, 7, 9, 3, 1] menghasilkan 12 (merampok rumah 0, 2, 4). Ini adalah masalah DP 1D klasik, dengan keputusan biner pada setiap langkah.
nums = [2, 7, 9, 3, 1]
# Can't rob adjacent houses
# Options: rob index 0 and 2 and 4 → 2+9+1=12
# or rob index 1 and 3 → 7+3=10
print('Max profit:', 12) # answer is 12Mendefinisikan Rekurensi
Misalkan dp[i] adalah jumlah maksimum uang yang dirampok dari i+1 rumah pertama. Pada setiap rumah i, Anda memiliki dua pilihan: melewatkannya (ambil dp[i-1]) atau merampoknya (ambil nums[i] + dp[i-2]). Rekurensinya adalah dp[i] = max(dp[i-1], nums[i] + dp[i-2]). Ini adalah pola dasar ambil-atau-lewati yang muncul dalam banyak masalah DP.
# Recurrence: dp[i] = max(dp[i-1], nums[i] + dp[i-2])
# Base cases:
# dp[0] = nums[0] (only one house, rob it)
# dp[1] = max(nums[0], nums[1]) (take the richer of the two)
def rob(nums):
n = len(nums)
if n == 1: return nums[0]
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i-1], nums[i] + dp[i-2])
return dp[-1]
print(rob([2, 7, 9, 3, 1])) # 12Menelusuri Tabel DP
Untuk [2, 7, 9, 3, 1], mari telusuri tabelnya: dp[0] = 2, dp[1] = max(2, 7) = 7, dp[2] = max(7, 9+2) = 11, dp[3] = max(11, 3+7) = 11, dp[4] = max(11, 1+11) = 12. Jawaban akhirnya adalah dp[4] = 12. Menelusuri tabel secara manual memastikan bahwa rekurensi menangani pengambilan dan pelewatan dengan benar pada setiap posisi.
nums = [2, 7, 9, 3, 1]
dp = [0] * len(nums)
dp[0] = 2
dp[1] = max(2, 7) # 7
for i in range(2, len(nums)):
skip = dp[i-1]
take = nums[i] + dp[i-2]
dp[i] = max(skip, take)
print(f'dp[{i}] = max({skip}, {nums[i]}+{dp[i-2]}) = {dp[i]}')
print('Answer:', dp[-1])Mengurangi Ruang menjadi O(1)
Tabel DP hanya melihat kembali dua posisi, sehingga kita dapat mengganti seluruh larik dengan dua variabel: prev2 (dua langkah sebelumnya) dan prev1 (satu langkah sebelumnya). Setelah setiap iterasi, kita menggesernya: prev2 = prev1 dan prev1 = current. Ini mengurangi penggunaan memori dari O(n) menjadi O(1) dengan tetap mempertahankan kompleksitas time O(n).
def rob_optimised(nums):
if not nums: return 0
if len(nums) == 1: return nums[0]
prev2 = nums[0]
prev1 = max(nums[0], nums[1])
for i in range(2, len(nums)):
curr = max(prev1, nums[i] + prev2)
prev2 = prev1
prev1 = curr
return prev1
print(rob_optimised([2, 7, 9, 3, 1])) # 12
print(rob_optimised([1, 2, 3, 1])) # 4Kasus Tepi yang Harus Ditangani
Selalu uji solusi Anda terhadap kasus tepi: larik kosong (kembalikan 0), larik satu elemen (kembalikan elemen tersebut), dan larik dua elemen (kembalikan nilai maksimum dari keduanya). Dalam wawancara, menyebutkan dan menangani kasus-kasus ini menunjukkan ketelitian. Penjaga if n == 1 mencegah indeks di luar batas saat mengakses nums[1] untuk dp[1].
def rob(nums):
if not nums: return 0
if len(nums) == 1: return nums[0]
prev2 = nums[0]
prev1 = max(nums[0], nums[1])
for i in range(2, len(nums)):
curr = max(prev1, nums[i] + prev2)
prev2, prev1 = prev1, curr
return prev1
print(rob([])) # 0
print(rob([5])) # 5
print(rob([3, 10])) # 10
print(rob([10, 3])) # 10Perampok Rumah II: Rumah Melingkar
Varian melingkar (LeetCode 213) menempatkan rumah dalam sebuah lingkaran, sehingga rumah pertama dan terakhir saling bersebelahan. Anda tidak dapat langsung menerapkan rekurensi linier. Wawasan utamanya adalah: Anda merampok rumah pertama dan mengecualikan rumah terakhir, atau mengecualikan rumah pertama dan menyertakan rumah terakhir. Jalankan algoritma perampok rumah linier pada kedua sub-larik, lalu ambil nilai maksimumnya.
def rob_linear(nums):
prev2, prev1 = 0, 0
for n in nums:
prev2, prev1 = prev1, max(prev1, n + prev2)
return prev1
def rob_circular(nums):
if len(nums) == 1: return nums[0]
# Either include first (exclude last) or include last (exclude first)
return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))
print(rob_circular([2, 3, 2])) # 3
print(rob_circular([1, 2, 3, 1])) # 4Mengapa Pendekatan Rakus Gagal di Sini
Pendekatan rakus yang naif mungkin selalu mencoba merampok rumah dengan nilai terbesar yang tersedia. Namun, pendekatan ini gagal pada masukan seperti [2, 1, 1, 2]: pendekatan rakus memilih rumah 0 (nilai 2) lalu rumah 3 (nilai 2) dengan total 4, tetapi merampok rumah 0 dan 2 juga menghasilkan 3. Tunggu — dalam kasus ini pendekatan rakus berhasil! Namun, coba [1, 3, 1, 3, 100]: pendekatan rakus memilih 3 dan 3 (indeks 1 dan 3) dengan total 6, sehingga melewatkan solusi optimal 1+1+100=102. DP diperlukan karena pilihan yang optimal secara lokal tidak menjamin optimum global.
# Greedy failure example
nums = [1, 3, 1, 3, 100]
# Greedy: pick max each step
# picks 3 (index 1), then 3 (index 3) → total 6
# DP optimal: pick 1 (index 0) + 1 (index 2) + 100 (index 4) → 102
def rob(nums):
prev2, prev1 = 0, 0
for n in nums:
prev2, prev1 = prev1, max(prev1, n + prev2)
return prev1
print(rob(nums)) # 102Mengenali Pola Ambil atau Lewati
Pola ambil atau lewati dapat digeneralisasikan melampaui masalah perampok rumah. Setiap kali Anda menelusuri larik dan pada setiap posisi memilih antara menyertakan elemen saat ini (serta melewati elemen sebelumnya) atau mengecualikannya (serta mempertahankan hasil sebelumnya), Anda menggunakan DP ambil atau lewati. Perhatikan batasan seperti tidak ada dua elemen yang bersebelahan atau tidak ada interval yang saling tumpang tindih sebagai tanda untuk menerapkan pola ini.
# General take-or-skip template
def take_or_skip(values, gap=1):
'''Max sum where selected elements must be at least gap+1 apart.'''
n = len(values)
if n == 0: return 0
# dp[i] = best up to index i
dp = [0] * (n + gap)
for i in range(n):
take = values[i] + (dp[i - 1] if i >= 1 else 0)
skip = dp[i + gap - 1] if i + gap - 1 < len(dp) else 0
dp[i + gap] = max(skip, take)
return dp[-1]
print(take_or_skip([2, 7, 9, 3, 1])) # house robber-likeVarian Hapus dan Dapatkan
Hapus dan Dapatkan (LeetCode 740) menanyakan hal berikut: untuk setiap angka yang Anda pilih, Anda memperoleh num × count(num), tetapi harus menghapus semua kemunculan num-1 dan num+1. Masalah ini dapat langsung direduksi menjadi perampok rumah: buat larik earn[v] = v × count(v) untuk semua nilai, lalu jalankan algoritma perampok rumah pada larik tersebut. Mengenali reduksi adalah keterampilan penting dalam wawancara.
from collections import Counter
def delete_and_earn(nums):
if not nums: return 0
count = Counter(nums)
max_val = max(nums)
# earn[v] = total points from taking all v's
earn = [v * count[v] for v in range(max_val + 1)]
# Now run house robber on earn
prev2, prev1 = 0, 0
for e in earn:
prev2, prev1 = prev1, max(prev1, e + prev2)
return prev1
print(delete_and_earn([3, 4, 2])) # 6 (take 3+3=no, take 4+2=6)
print(delete_and_earn([2, 2, 3, 3, 3, 4])) # 9 (take all 3s)Perampok Rumah III: Pohon Biner
Dalam Perampok Rumah III, rumah-rumah disusun sebagai pohon biner. Anda tidak dapat merampok sebuah simpul dan induk langsungnya secara bersamaan. Definisikan fungsi pembantu yang mengembalikan dua nilai: rob(node) → (rob_root, skip_root). Jika Anda merampok akar, jumlahkan nilai yang melewati kedua anaknya. Jika Anda melewati akar, jumlahkan nilai terbaik dari setiap anak. Ini adalah DFS pascaurutan dengan keputusan ambil atau lewati pada setiap simpul.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def rob_tree(root):
def dfs(node):
if not node: return (0, 0) # (rob, skip)
l_rob, l_skip = dfs(node.left)
r_rob, r_skip = dfs(node.right)
rob = node.val + l_skip + r_skip
skip = max(l_rob, l_skip) + max(r_rob, r_skip)
return (rob, skip)
return max(dfs(root))
# Tree: 3 -> 2,3 -> None,3,None,1
root = TreeNode(3, TreeNode(2, None, TreeNode(3)), TreeNode(3, None, TreeNode(1)))
print(rob_tree(root)) # 7Kompleksitas dan Pembahasan Wawancara
Perampok rumah linier berjalan dalam O(n) time dan O(1) ruang dengan optimasi dua variabel. Varian melingkar juga berjalan dalam O(n) time karena memanggil versi linier dua kali. Varian pohon berjalan dalam O(n) time dan ruang O(h), dengan h sebagai tinggi pohon. Dalam wawancara, selalu nyatakan kompleksitas setelah menulis kode dan sebutkan optimasi ruang — ini menunjukkan bahwa Anda berpikir melampaui solusi pertama yang berhasil.
# Summary of complexities
# Linear House Robber:
# Time: O(n), Space: O(1) with two-variable trick
# Circular House Robber:
# Time: O(n), Space: O(1) (two passes)
# Tree House Robber:
# Time: O(n), Space: O(h) call stack
# Quick benchmark
import time
import random
nums = [random.randint(0, 100) for _ in range(10**6)]
start = time.time()
prev2 = prev1 = 0
for n in nums:
prev2, prev1 = prev1, max(prev1, n + prev2)
print(f'1M elements in {time.time()-start:.3f}s, result={prev1}')Pemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Pada pelajaran ini Anda mempelajari: relasi rekurensi ambil atau lewati dp[i] = max(dp[i-1], nums[i] + dp[i-2]), mengurangi ruang O(n) menjadi O(1) dengan dua variabel bergulir, dan memperluas pola ke larik melingkar dan pohon biner. Selanjutnya kita membahas masalah Sublarik Maksimum dan Sublarik Hasil Kali Maksimum menggunakan algoritma Kadane.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “House Robber: Rekurensi Ambil atau Lewati” gratis?
Ya — teks lengkap “House Robber: Rekurensi Ambil atau Lewati” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus DSA Interview Prep, upgrade ke CoddyKit PRO. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “House Robber: Rekurensi Ambil atau Lewati”?
Modelkan keputusan mengambil atau melewati sebagai relasi rekurensi DP, kurangi ruang menjadi dua variabel, lalu perluas solusi ke rumah-rumah melingkar. Kamu berlatih DSA 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 DSA Interview Prep?
Tidak diperlukan pengalaman sebelumnya. DSA 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 1 dari 4.
Berapa lama pelajaran “House Robber: Rekurensi Ambil atau Lewati” 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 DSA Interview Prep ini?
Ya. Setiap pelajaran DSA 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
- House Robber: Rekurensi Ambil atau Lewati
- Subarray Maksimum dan Subarray Produk Maksimum
- Word Break dan Segmentasi String
- Decode Ways dan Penghitungan Jalur