题解 | #打家劫舍(一)#

package com.hhdd.dp;

/**
 * @Author huanghedidi
 * @Date 2022/8/6 12:36
 */
public class 打家劫舍1 {

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

    /**
     * dp[i]表示一定偷第i家带来的最大值
     * 递推公式是i-1前面找出最大的再加上i的金额
     *
     * @param nums
     * @return
     */
    public static int rob(int[] nums) {
        // 数组长度小于3位的情况其实都不用考虑
        if (nums.length <= 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        // write code here
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = nums[1];
        dp[2] = dp[0] + nums[2];
        // i位置的值要么是i-2位置 或i-3 位置递推来，不会有其他情况
        for (int i = 3; i < nums.length; i++) {
            dp[i] = Math.max(dp[i], dp[i - 2] + nums[i]);
            dp[i] = Math.max(dp[i], dp[i - 3] + nums[i]);
        }
        return Math.max(dp[nums.length - 1], dp[nums.length - 2]);
    }


}