导读 最近刷LeetCode时遇到一道经典问题——House Robber(0198)!😊 这道题讲述了一个小偷的故事:他想从一排房子中偷钱,但不能连续进入两...
最近刷LeetCode时遇到一道经典问题——House Robber(0198)!😊 这道题讲述了一个小偷的故事:他想从一排房子中偷钱,但不能连续进入两户人家,否则会触发警报。如何才能最大化收益呢?🤔
首先,我们定义状态 `dp[i]` 表示到第 `i` 户人家时能偷到的最大金额。如果选择偷当前这家,那么就不能偷上一家;如果不偷当前这家,则可以继承前一家的最大值。公式如下:
`dp[i] = max(dp[i-1], dp[i-2] + nums[i])`
通过这个递推关系,我们可以轻松找到最优解!🌟 实际编码时只需用两个变量存储前两户的状态即可优化空间复杂度。👀
这道题不仅考验逻辑思维,还教会了我们如何用动态规划解决问题。😎 如果你也对算法感兴趣,不妨一起挑战更多有趣的题目吧!💪✨