题解 | #打家劫舍(一)#
打家劫舍(一)
https://www.nowcoder.com/practice/c5fbf7325fbd4c0ea3d0c3ea6bc6cc79
动态规划,每一个房间都有两种选择,偷或者不偷
- 偷,偷了当前房间dp[i],则收益为dp[i-2]+nums[i]
- 不偷,收益不变,为dp[i-1]
所以 dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1])
用l2来表示dp[i-2],l1来表示dp[i-1],节约空间
import java.util.*; public class Solution { public int rob (int[] nums) { // write code here int l2=0,l1=0,l=0,res=0; for(int num:nums){ l = Math.max(l2+num,l1); res = Math.max(res,l); l2 = l1; l1 = l; } return res; } }