LeetCode之打家劫舍

1. 问题

2. 示例

3. 思路

　　对于此题，如果只有两家或者以下，我们选择金额最大的。如果2家以上，那我们打劫到第 i 家的时候，就要考虑，要不要打劫这一家，也就是（这一家的价值+打劫到 i - 2家的最大价值）和（打劫到上一家（i - 1）的最大价值），比较这两个值，选较大值作为打劫到第 i 家的最大价值。最后输出最后一家就可以了。

4. 代码实现

package com.emotiv.code;

/**
 * @Author: JLU Tiger
 * @Date: 2019/11/22 9:26
 */
public class Answer {
    public static int rob(int[] nums) {
        if (nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        // 每次做数组判定时都需要做数组边界判定，防止越界
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);
        // 当两家以上时，打劫到第i家的时候，就要考虑要不要打劫这一家，也就是（这一家的价值+打劫到i-2家的最大价值）
        // 和（打劫到i-1家的最大价值），比较这两个值，选较大值作为打劫到i的最大值
        for (int i = 2; i < nums.length; i++) {
            dp[i] = ((nums[i] + dp[i - 2]) > dp[i - 1]) ? (nums[i] + dp[i - 2]) : dp[i - 1];
        }
        return dp[nums.length - 1];
    }

    public static void main(String[] args) {
        int[] nums = {1,2,3,1};
        System.out.println(rob(nums));
    }
}