题解 | 打家劫舍(二)

import java.util.*;


public class Solution {

    public int rob (int[] nums) {
        int n=nums.length;
        return Math.max(method(nums,0,n-2),method(nums,1,n-1));
    }
    public int method (int[] nums,int start,int end) {
        int n=end-start+1;
        if (end==start)return nums[start];
        int []dp = new int [n + 1];
        //dp[i]为下标i为止的最大金额
        //dp[i]=max(nums[i]+dp[i-2],dp[i-1])
       
        dp[start] = nums[start];
        dp[start+1] = Math.max(nums[start], nums[start+1]);
        for (int i = 2; i <= end; i++) {
            dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]) ;
        }

        return dp[end];
    }
}