题解 | #打家劫舍(二)#
打家劫舍(二)
http://www.nowcoder.com/practice/a5c127769dd74a63ada7bff37d9c5815
/*
当前家不偷或偷
当前不偷所获最大利润 = max(前一天不偷，前一天偷)；
dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
当前偷所获最大利润 = 前一天没偷 + 今日所得
dp[i][1] = dp[i-1][0] + nums[i];
环形问题，分两种情况讨论：
第一种情况，偷或不偷第一家，确保不偷最后一家；
第二种情况，确保不偷第一家，最后一家偷或不偷。
*/
int max(int a, int b){
if(a>b) return a;
else return b;
}
int rob(int* nums, int numsLen ) {
int dp[numsLen][2];
memset(dp,0,sizeof(dp));
//第一种情况，偷或不偷第一家，不偷最后一家
dp[0][0] = 0;
dp[0][1] = nums[0];
for(int i = 1; i < numsLen-1; i++){
dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
dp[i][1] = dp[i-1][0] + nums[i];
}
int ret1 = max(dp[numsLen-2][0],dp[numsLen-2][1]);
//第二种情况，不偷第一家，最后一家偷或不偷。
memset(dp,0,sizeof(dp));
dp[0][0] = 0;
dp[0][1] = 0;
for(int i = 1; i < numsLen; i++){
dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
dp[i][1] = dp[i-1][0] + nums[i];
}
int ret2 = max(dp[numsLen-1][0],dp[numsLen-1][1]);
return max(ret1,ret2);
}
