代码随想录算法训练营动态规划part08

一、打家劫舍

设动态规划列表 dp，dp[i] 代表前 i 个房子在满足条件下的能偷窃到的最高金额。
设：有 n 个房子，前 n 间能偷窃到的最高金额是 dp[n]，前 n−1 间能偷窃到的最高金额是 dp[n−1] ，此时向这些房子后加一间房，此房间价值为 num ；
加一间房间后：由于不能抢相邻的房子，意味着抢第 n+1 间就不能抢第 n 间；那么前 n+1 间房能偷取到的最高金额 dp[n+1]一定是以下两种情况的较大值： 1.不抢第 n+1 个房间，因此等于前 n 个房子的最高金额，即dp[n+1]=dp[n] ； 2.抢第 n+1 个房间，此时不能抢第 n 个房间；因此等于前 n−1 个房子的最高金额加上当前房间价值，即 dp[n+1]=dp[n−1]+num ；
最终的转移方程： dp[n+1]=max(dp[n],dp[n−1]+num)
初始状态：前 0 间房子的最大偷窃价值为 0 ，即 dp[0]=0 。
返回值：返回 dp 列表最后一个元素值，即所有房间的最大偷窃价值。


class Solution {
    public int rob(int[] nums) {
        int pre = 0, cur = 0, tmp;
        for(int num : nums) {
            tmp = cur;
            cur = Math.max(pre + num, cur);
            pre = tmp;
        }
        return cur;
    }
}

二、打家劫舍II

213. 打家劫舍 II - 力扣（LeetCode）


class Solution {
    public int rob(int[] nums) {
        if(nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];
        return Math.max(myRob(Arrays.copyOfRange(nums, 0, nums.length - 1)), 
                        myRob(Arrays.copyOfRange(nums, 1, nums.length)));
    }
    private int myRob(int[] nums) {
        int pre = 0, cur = 0, tmp;
        for(int num : nums) {
            tmp = cur;
            cur = Math.max(pre + num, cur);
            pre = tmp;
        }
        return cur;
    }
}

三、打家劫舍III

337. 打家劫舍 III - 力扣（LeetCode）


class Solution {
    public int rob(TreeNode root) {
        int[] rootStatus = dfs(root);
        return Math.max(rootStatus[0], rootStatus[1]);
    }
 
    public int[] dfs(TreeNode node) {
        if (node == null) {
            return new int[]{0, 0};
        }
        int[] l = dfs(node.left);
        int[] r = dfs(node.right);
        int selected = node.val + l[1] + r[1];
        int notSelected = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
        return new int[]{selected, notSelected};
    }
}

相关阅读:
linux centos出现No space left on device解决方案
MybatisPlus拓展——实现多数据源操作
C# 11新特性之原始字符串
2022Android开发面试（备战金九银十题库+小技巧）
How to boot the Raspberry Pi system from a USB Mass Storage Device All In One
SpringCloud - OpenFeign 参数传递和响应处理（全网最详细）
【React扩展】2、PureComponent、ErrorBoundary、render props和组件通信方式总结
C#面：可以在C#静态类中使用“this”吗？
mysql某批量更新导致死锁
CI/CD——Jenkins自动构建maven项目

原文地址：https://blog.csdn.net/m0_63297917/article/details/133178498

代码随想录算法训练营 动态规划part08

一、打家劫舍

二、打家劫舍II

三、打家劫舍III

代码随想录算法训练营动态规划part08