题目描述
分析
1. 动态规划
dp[n] = MAX(dp[n-1], dp[n-2]+num)
dp[n]是最终获取金额最多的数值；第n间房子，其最大数额是dp(n-1)或是dp[n-2]+num,num是第n间房子的金额
代码实现
public enum Q198 {
instance;
public int rob(int[] nums) {
if(nums==null||nums.length==0)return 0;
if(nums.length==1)return nums[0];
int[] dp=new int[nums.length];
dp[0]=nums[0];
//dp[1]=MAX(dp[0],dp[n-2]+num)
dp[1]=MAX(dp[0],0+nums[1]);
int n=2;
for(;n<nums.length;n++){
int num=nums[n];
//dp[n]=MAX(dp[n-1],dp[n-2]+num)
dp[n]=MAX(dp[n-1],dp[n-2]+num);
}
return dp[n-1];
}
private int MAX(int a,int b){
return a>b?a:b;
}
public static void main(String[] args) {
// assert 4
SystemUtil.print(Q198.instance.rob(new int[]{1,2,3,1}));
// assert 12
SystemUtil.print(Q198.instance.rob(new int[]{2,7,9,3,1}));
// assert 4
SystemUtil.print(Q198.instance.rob(new int[]{2,1,1,2}));
}
}
