LeetCode 198：打家劫舍

链接
题目：

思路：动态规划

• dp定义：以start为起点，可以偷的最多的钱是多少, 所求即 dp(nums,0) ；

• 状态和选择：
  状态：就是起点start，即小偷所处的位置即nums数组的索引；
  选择：当前要么抢，要么不抢，如果不抢则start想前走+1，如果抢，则要加上当前nums中start位置的钱，然后start+2 ！

• base case：
  如果 start > nums.lenth-1 ，则为0 ，即起点超过最后一家就抢不到了；

• 重叠子问题

class Solution {
    
    int memo[];
    public int rob(int[] nums) {
    
        memo=new int[nums.length];
        Arrays.fill(memo,-1); // 初始化dp
        return dp(nums,0);
        // memo定义：从 i出发能抢到最多的钱总数
    }

    int dp(int[] nums,int start){
     // start就对应题目数组的索引；
        // base case ，即start超过最后一间房子后，抢到的为0
        if(start>=nums.length){
    
            return 0;
        }

        // 重叠子问题
        if(memo[start]!=-1){
    
            return memo[start];
        }
        // 状态转移（选择）：不抢 or 抢
        memo[start]=Math.max( dp(nums,start+1) , dp(nums,start+2)+nums[start] );
        return memo[start];
    }

}