力扣第LCR 089题-打家劫舍

题目链接

class Solution {
    /*
    * 状态转移公式：dp[i] = num[i - 1] + nums[i], 如果 i - 1 没被偷
    *                      max(dp[i - 2] + nums[i], dp[i - 1]), 如果 i - 1 被偷了
    * */
    public int rob(int[] nums) {
        int len = nums.length;
        // 记录状态
        int[] dp = new int[len];
        // 记录当前值是否被记录（是否被偷）
        boolean[] steal = new boolean[len];
        // 初始化状态
        dp[0] = nums[0];
        steal[0] = true;
        for (int i = 1; i < len; i++) {
            // 相邻被偷
            if (steal[i - 1]) {
                // 计算偷当前之后的状态值
                int st = ((i - 2 >= 0) ? dp[i - 2] : 0) + nums[i];
                // 比较偷当前和不偷当前谁的状态大
                dp[i] = Math.max(st, dp[i - 1]);
                steal[i] = st > dp[i - 1];
            }
            // 相邻没被偷
            else {
                // 当前状态等于前一个状态加上当前值
                dp[i] = dp[i - 1] + nums[i];
                steal[i] = true;
            }
        }
        return dp[len - 1];
    }
}