534. House Robber II

三个入室抢劫的题这题我最喜欢。I太直接,III是脑筋急转弯会了不难,还是II最好。最有意思的地方是你怎么给II定义它的DP数组,一开始着实没想太透彻,因为是相当于把原数组取了一个子数组出来做DP。

还有一点就是house robber的dp数组不需要长度加1。第几个dp就是表明了第几个房子抢或不抢的收益。这不禁让我反思到底那些题目需要定义长度加一的DP数组。目前的结论是,比如那些字符串匹配的需要考虑空串的,求sum的时候没有数字的,都需要加,包括背包问题空间为0的时候。

这道题不用加1使问题更加简单。之前的疑问也稍微好办了,就还是一个全局的dp数组,不同子数组无所谓啊,我还是按照起index对整个dp数组进行操作就好。只要最后返回正确的dp里的数字就好

return Math.max(helper(nums,0,nums.length-2), helper(nums, 1, nums.length-1));
 }
 
 public int helper(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-1], dp[i-2] + nums[i]);
 }
 
 return dp[end];
 }

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.