題目描述
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
題目本質(zhì)：求一個數(shù)組中元素的最大和迂烁，但是元素不能從連續(xù)的位置取递鹉。可用動態(tài)規(guī)劃的思想解決：保存在每個位置時躏结，加上當(dāng)前元素和不加當(dāng)前元素能得到的最大元素和。
public class Solution {
public int rob(int[] nums) {
if(nums.length == 0)
return 0;
int[][] dp = new int[nums.length][2];
//0表示不被搶劫黄橘，1表示被搶劫
for(int i = 0; i < dp.length; i++){
dp[i][0] = 0;
dp[i][1] = 0;
}
dp[0][0] = 0;
dp[0][1] = nums[0];
for(int i = 1; i < dp.length; i++){
//如果不加入屈溉，保持搶劫到前一家時的最大和；如果加入语婴，上一家必須沒有被搶劫過
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]);
dp[i][1] = dp[i-1][0] + nums[i];
}
return Math.max(dp[dp.length-1][0], dp[dp.length-1][1]);
}
}
還有更簡單的方法：用temp0表示不搶劫此家的最大和，temp1表示搶劫此家的最大和匿醒。
public class Solution {
public int rob(int[] nums) {
if(nums.length == 0)
return 0;
int temp0 = 0, temp1 = nums[0];
int temp = 0;
for(int i = 1; i < nums.length; i++){
temp = Math.max(temp0, temp1);
temp1 = temp0 + nums[i];
temp0 = temp;
}
return Math.max(temp0, temp1);
}
}
