题解 | #打家劫舍(二)#
打家劫舍(二)
https://www.nowcoder.com/practice/a5c127769dd74a63ada7bff37d9c5815
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @return int整型
*/
public int rob (int[] nums) {
// write code here
if(nums == null || nums.length == 0)return 0;
if(nums.length == 1)return nums[0];
return Math.max(robRange(nums, 0, nums.length-2), robRange(nums, 1, nums.length-1));
}
private int robRange(int[] nums, int start, int end){
if(start == end)return nums[start];
int[] dp = new int[nums.length];
dp[start] = nums[start];
dp[start+1] = Math.max(nums[start], nums[start+1]);
for(int i = start+2; i <= end; i++){
dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1]);
}
return dp[end];
}
}
分两种情况，包括第一个元素但不包括最后一个、包括最后一个但不包括第一个
投递腾讯等公司7个岗位 >
