Day 23：House Robber (LeetCode #198) - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天

2025 iThome 鐵人賽

0

自我挑戰組

Java × LeetCode-30天日記系列第 23 篇

Day 23：House Robber (LeetCode #198)

17th鐵人賽

2025-10-16 10:28:05

56 瀏覽

分享至

題目理解
我的理解： 是一個小偷，要從一排房子中偷錢，每間房子有一定金額，但不能偷相鄰的兩間。
方法

定義 dp[i] 為「考慮到第 i 間（包含 i），在前 i+1 間房子能偷到的最大金額」。
對第 i 間，你有兩個選擇：
1.不偷第 i 間 → 最大值是 dp[i-1]。
2.偷第 i 間 → 最大值是 dp[i-2] + nums[i]（因為不能偷第 i-1）。
因此轉移式是：dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])。
初始：
dp[0] = nums[0]
dp[1] = Math.max(nums[0], nums[1])（若存在第二間）

心得
這題讓我理解到 DP 的核心在於「記住子問題的最佳解」。DP 讓我一步步建立結果，像是「滾動式累積」，效率提升非常明顯。

Day 22：Maximum Subarray (LC #53)

Day 24：Coin Change (LeetCode #322)

系列文

Java × LeetCode-30天日記共 30 篇

目錄

RSS系列文訂閱系列文

0 人訂閱

完整目錄

熱門推薦

{{ item.subject }}

{{ item.channelVendor }} | {{ item.webinarstarted }} |

{{ formatDate(item.duration) }}

直播中

尚未有邦友留言

立即登入留言

參賽組數

902 組

團體組數

37 組

累計文章數

19652 篇

完賽人數

530 人

15th鐵人賽 16th鐵人賽 13th鐵人賽 14th鐵人賽 17th鐵人賽 12th鐵人賽 11th鐵人賽鐵人賽 2019鐵人賽 javascript 2018鐵人賽 python 2017鐵人賽 windows php c# linux windows server css react

IT邦幫忙