题目链接
    image.png
    取下标不相邻的数字。

    1. class Solution {
    2.     // 迭代 。。 优化，可以将两个数字来存，降低空间复杂度    
    3.     public int rob(int[] nums) {
    4.         if(nums.length == 1) return nums[0];
    6.         int[] arr = new int[nums.length];
    8.         arr[0] = nums[0];
    9.         arr[1] = Math.max(nums[0],nums[1]);
    11.         for(int i = 2; i < nums.length; i++) {
    12.             arr[i] = Math.max(arr[i-1], arr[i-2]+nums[i]);
    13.         }
    15.         return arr[nums.length-1];
    16.     }
    19.     // 递归。超时
    20.     public int rob(int[] nums) {
    21.         return resursion(nums.length-1, nums);
    22.     }
    24.     public int resursion(int index, int[] arr) {
    25.         if(index < 0) return 0; 
    27.         if(index == 0) return arr[0];
    29.         return Math.max(resursion(index-1,arr), resursion(index-2,arr)+arr[index]); 
    30.     }
    31. }