Leetcode 198. House Robber

tags: Leetcode(JAVA)

題目 : https://leetcode.com/problems/house-robber/ 。

想法 :

​​​​DP ! DP ! DP !
​​​​dp[n] = max(dp[n-1], dp[n-2] + h[n]);

時間複雜度 : O(n)。

程式碼 : (JAVA)

class Solution {
    public int rob(int[] nums) {
        int l=nums.length;
        if(l == 1) return nums[0];
        if(l == 2) return Math.max(nums[0], nums[1]);
        
        int[] dp=new int[l];
        
        dp[0]=nums[0]; 
        dp[1]=Math.max(nums[0], nums[1]);
        
        for(int i=2 ; i<l ; i++){
            dp[i]=Math.max(dp[i-1], dp[i-2]+nums[i]);
        }
        
        return dp[l-1];
    }
}