Leetcode 打家劫舍
这道题是典型的“打家劫舍”问题,算法思想是动态规划(Dynamic Programming)。我们需要计算在不触动相邻房屋警报装置的情况下,小偷能偷到的最大金额。具体算法思想如下:
1. 问题分析:
- 偷取限制:如果小偷偷了某一间房子,则不能偷与这间房子相邻的房子。
- 目标:从一系列房屋中,计算出小偷能偷到的最大金额。
2. 动态规划(DP)的思想:
我们通过动态规划来解决这个问题,即通过存储之前的计算结果,来避免重复计算,从而提高效率。
状态定义:
设 dp[i]
表示前 i
个房屋能偷取的最大金额。那么,对于每个房屋,我们有两种选择:
- 不偷当前房屋 i:那么最大金额是
dp[i-1]
,即上一个房屋的最大偷取金额。 - 偷当前房屋 i:那么最大金额是
dp[i-2] + nums[i]
,即偷取当前房屋 i,加上不相邻的房屋(即房屋i-2
)的最大金额。
因此,递推关系可以表示为:
dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])
其中 dp[i-1]
是不偷当前房屋,dp[i-2] + nums[i]
是偷当前房屋。
初始状态:
dp[0] = nums[0]
,只有一个房屋时,能偷的最大金额就是第一个房屋的金额。dp[1] = Math.max(nums[0], nums[1])
,当有两个房屋时,小偷只能选择金额较大的那个房屋偷取。
最终结果:
dp[nums.length - 1]
就是所有房屋中能偷取的最大金额。
3. 代码解释:
class Solution {
public int rob(int[] nums) {
if(nums.length == 1) {
return nums[0];
}
int[] dp = new int[nums.length];
//定义状态转移方程, dp[i]表示前i个房间所能够偷窃到的最高金额
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for(int i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[nums.length - 1];
}
}
4. 时间复杂度与空间复杂度:
- 时间复杂度:O(n),其中
n
是房屋的数量。每个房屋只需计算一次,时间复杂度为线性。 - 空间复杂度:O(n),因为我们使用了一个长度为
n
的数组dp
来存储每个房屋的最大金额。
该算法通过动态规划,有效地避免了重复计算,确保了在给定的约束下,小偷能获得的最大金额。
原文地址:https://blog.csdn.net/coldasice342/article/details/142753287
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!