- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
先明确题意，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警，所以我们得隔着偷。
最优子结构
从 n 个房子中能偷到的最大金额，f(n)。
- 偷前 n - 1 间房子，最后一间房子不偷
- 偷前 n - 2 间房子和最后一间房子
状态转移方程
Math.max(dp[i - 1], dp[i - 2] + nums[i - 1])
处理边界条件
- n = 0，没有房子，所以
dp[0] = 0 - n = 1，只有一个房子，偷就完了，
dp[1] = nums[0]
constrob=function(nums){constn=nums.lengthif(n===0)return0constdp=newArray(n)dp[0]=0dp[1]=nums[0]for(leti=2;i<=n;i++){dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i-1])}returndp[n]}
降维，空间优化
其实，我们实际上只用到了 f(n - 1) 和 f(n - 2) 的结果，并不需要始终持有整个DP数组，每一步只需要前两个最大值，所以两个变量就足够用了。
constrob=function(nums){constn=nums.lengthif(n===0)return0letprev=0letcurr=0for(leti=0;i<n;i++){lettmp=currcurr=Math.max(curr,prev+nums[i])prev=tmp}returncurr}
- 时间复杂度：O(n)
- 空间复杂度：O(1)