House Robber
Rumah-rumah berdiri berjajar di sepanjang jalan, dan nums[i] adalah uang di rumah i. Kamu boleh mengambil uang dari rumah mana pun yang kamu pilih, tetapi jangan pernah mengambil uang dari dua rumah yang berdiri berdampingan. Kembalikan jumlah total terbesar yang bisa kamu ambil.
Fungsi
- numsinteger-array
- uang di setiap rumah, sesuai urutan jalan
- Mengembalikaninteger
- total terbesar yang bisa kamu ambil tanpa mengambil dari dua rumah yang bersebelahan
Batasan
1 ≤ nums.length ≤ 1040 ≤ nums[i] ≤ 1000- Jawabannya paling banyak
5 × 106, jadi muat dalam integer 32-bit bertanda.
Contoh
- Input
- nums = [5, 3, 4, 11, 2]
- Output
- 16
- Penjelasan
- Ambil 5 dan 11 dari rumah 0 dan 3 sehingga menjadi 16. Kamu boleh melewati dua rumah berturut-turut, dan cara ini mengalahkan semua rencana lainnya: 5 + 4 + 2 = 11 dan 3 + 11 = 14.
- Input
- nums = [3, 10, 3]
- Output
- 10
- Penjelasan
- Dua rumah di ujung jika dijumlahkan menghasilkan 3 + 3 = 6. Rumah di tengah saja menghasilkan 10, dan memilihnya membuat kedua rumah tetangganya tidak bisa dipilih.
- Input
- nums = [2, 9, 3, 1, 8]
- Output
- 17
- Penjelasan
- 9 dan 8 berada di rumah 1 dan 4, yang bukan tetangga, sehingga hasilnya 17. Mengambil rumah selang-seling dari awal hanya menghasilkan 2 + 3 + 8 = 13.
Pertanyaan lanjutan
Kembalikan rumah-rumah yang akan diambil beserta jumlah totalnya. Apa yang harus kamu simpan dari tabel untuk menyusun kembali daftar itu, dan apakah dua total berjalan masih bisa melakukannya?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Lihat rumah terakhir. Sebuah rencana akan mengambilnya atau melewatkannya. Apa yang harus kamu selesaikan setelah setiap pilihan?
Jika kamu melewati rumah
k-1, hasil terbaik adalah hasil terbaik darik-1rumah pertama. Jika kamu mengambilnya, tambahkannums[k-1]ke hasil terbaik darik-2rumah pertama. Jawaban untukkrumah adalah nilai yang lebih besar dari keduanya.Isi total terbaik itu dari awal jalan, dimulai dengan 0 saat belum ada rumah. Setiap total hanya membutuhkan dua total sebelumnya, jadi dua variabel sudah cukup.
Solusi
Jalan pintas gagal: mengambil satu rumah selang satu membuatmu melewatkan 5 dan 11 dalam [5, 3, 4, 11, 2], dan mengambil rumah terkaya terlebih dahulu menghasilkan total yang lebih kecil pada [3, 4, 3]. Tentukan pilihan untuk satu rumah setiap kali: total terbaik hingga suatu rumah hanya bergantung pada total terbaik hingga dua rumah sebelumnya.
Coba kedua pilihan di setiap rumah
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
Setiap rencana melewatkan rumah terakhir atau mengambilnya. Jika dilewatkan, rencana terbaik untuk n-1 rumah pertama tetap menjadi yang terbaik. Jika diambil, nums[n-1] ditambahkan ke rencana terbaik untuk n-2 rumah pertama. Jadi, most(k) = max(most(k-1), most(k-2) + nums[k-1]), dengan most(0) = 0 dan most(1) = nums[0]. Kedua cabang mencakup semua rencana, jadi jawabannya benar.
Kedua cabang saling tumpang tindih: most(k-1) kembali meminta most(k-2), dan jumlah pemanggilan bertambah seperti deret Fibonacci, sekitar 1.6^n. Empat puluh rumah membutuhkan lebih dari 300 juta pemanggilan, dan n mencapai 10^4.
Algoritma
- Tulis helper
most(k)yang mengembalikan jumlah maksimum yang bisa kamu ambil darikrumah pertama. - Kembalikan 0 jika
kadalah 0, dannums[0]jikakadalah 1. - Jika tidak, hitung
skip = most(k-1)dantake = most(k-2) + nums[k-1]. - Kembalikan nilai yang lebih besar dari keduanya. Jawabannya adalah
most(n).
def rob(nums):
def most(k):
# The most you can take from the first k houses
if k == 0:
return 0
if k == 1:
return nums[0]
# Skip house k-1, or take it and skip house k-2
return max(most(k - 1), most(k - 2) + nums[k - 1])
return most(len(nums))Tabel bottom-up
Intuisi
Rekursi hanya menanyakan most(0) sampai most(n): n + 1 pertanyaan. Jawab setiap pertanyaan sekali dalam tabel best, mulai dari best[0] = 0 dan best[1] = nums[0], lalu isi dari bawah ke atas mulai dari k = 2, sehingga kedua entri yang dibaca setiap jawaban sudah tersedia.
Untuk [5, 3, 4, 11, 2], tabelnya adalah 0, 5, 5, 9, 16, 16. Pada k = 4, melewati rumah 3 mempertahankan best[3] = 9, sedangkan mengambil 11 ditambah best[2] = 5 menghasilkan 16, yang lebih besar. Setiap entri memerlukan satu perbandingan: waktu O(n) dan ruang O(n).
Algoritma
- Buat tabel
bestdengan n + 1 entri. - Tetapkan
best[0] = 0danbest[1] = nums[0]. - Untuk
kdari 2 hingga n, tetapkanbest[k]ke nilai yang lebih besar antarabest[k-1]danbest[k-2] + nums[k-1]. - Kembalikan
best[n].
def rob(nums):
n = len(nums)
# best[k] is the most you can take from the first k houses
best = [0] * (n + 1)
best[1] = nums[0]
for k in range(2, n + 1):
# Skip house k-1, or take it on top of the best from the first k-2 houses
best[k] = max(best[k - 1], best[k - 2] + nums[k - 1])
return best[n]Dua total berjalan
Intuisi
Setiap entri hanya membaca dua entri sebelumnya, jadi gunakan dua angka, bukan tabel: twoBack dan oneBack, total terbaik hingga dua rumah sebelumnya dan hingga rumah sebelumnya. Untuk rumah yang menyimpan x, nilai terbaik yang baru adalah max(oneBack, twoBack + x); lalu geser keduanya. Keduanya dimulai dari 0, yaitu jalan kosong sebelum rumah pertama, jadi jalan dengan satu rumah tidak memerlukan kasus khusus. Waktu tetap O(n), dan penggunaan memori turun menjadi O(1).
Algoritma
- Atur
twoBackdanoneBackke 0. - Untuk setiap jumlah
xdinums, hitungcurrent = max(oneBack, twoBack + x). - Pindahkan
oneBackketwoBack, lalucurrentkeoneBack. - Setelah rumah terakhir, kembalikan
oneBack.
def rob(nums):
# The best totals from the houses up to two back and up to one back
two_back, one_back = 0, 0
for amount in nums:
# Skip this house, or take it on top of the best from two back
two_back, one_back = one_back, max(one_back, two_back + amount)
return one_back
Jebakan dan kasus tepi
- Menimpa
oneBacksebelum menyalinnya ketwoBack. Rumah berikutnya lalu membaca total yang salah. Hitung nilai terbaik yang baru terlebih dahulu, lalu geser, atau tetapkan keduanya sekaligus. - Membaca
nums[1], atau menetapkanbest[1]danbest[2]sejak awal. Keduanya gagal untuk jalan yang hanya memiliki satu rumah, seperti[0]. - Di Lua dan R, indeks array dimulai dari 1, jadi uang di rumah
k-1ada dinums[k].
Pertanyaan yang sering diajukan3
Apa kompleksitas waktu dan ruang dari House Robber?
Dynamic programming memeriksa setiap rumah satu kali, sehingga membutuhkan waktu O(n). Tabel lengkap menggunakan ruang O(n), dan hanya menyimpan dua total terakhir menguranginya menjadi O(1). Rekursi biasa tanpa menyimpan jawaban menghasilkan sekitar 1.6^n pemanggilan.
Mengapa mengambil rumah secara selang-seling tidak menyelesaikan masalah Perampok Rumah?
Rencana terbaik terkadang melewati dua rumah berturut-turut. Dalam [10, 1, 1, 10], rumah-rumah bernomor genap dan rumah-rumah bernomor ganjil sama-sama berjumlah 11, sedangkan rumah pertama dan terakhir berjumlah 20.
Bagaimana cara menyelesaikan House Robber ketika rumah-rumahnya membentuk lingkaran?
Dalam lingkaran, rumah pertama dan terakhir bertetangga, jadi rencana hanya mengambil paling banyak salah satunya. Jalankan solusi untuk jalan lurus dua kali, sekali tanpa rumah terakhir dan sekali tanpa rumah pertama, lalu kembalikan hasil yang lebih besar. Satu rumah adalah kasus khusus: jawabannya adalah rumah tersebut.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def rob(nums):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
nums = [5, 3, 4, 11, 2]
Output yang diharapkan
16