算法--2023.1.15

1.力扣198--打家劫舍

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = nums[0];
        //状态转移：
        //遍历到第i个节点，比较遍历到前一个节点与前两个节点加上当前节点的最大值，最为第i个节点的值
        for(int i = 2;i<=n;i++){
            dp[i] = Math.max(nums[i-1]+dp[i-2],dp[i-1]);
        }
        return dp[n];
    }
}

2.力扣213--打家劫舍2

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n == 1){
            return nums[0];
        }
        //原理同上，在此基础上，增加一个dp数组
        int[] dp1 = new int[n+1];
        //第二个dp数组遍历到第一个节点的时候，dp[1]设置为0代表不用低一个节点的值，这样就一定可以用最后一个节点
        int[] dp2 = new int[n+1];
        dp1[0] = 0;dp1[1] = nums[0];
        dp2[0] = 0;dp2[1] = 0;
        for(int i = 2; i<= n;i++){
            dp1[i] = Math.max(dp1[i-2]+nums[i-1],dp1[i-1]);
            dp2[i] = Math.max(dp2[i-2]+nums[i-1],dp2[i-1]);
        }
        //返回的时候，比较dp1倒数第二个节点与dp2的最后一个节点
        //两种情况：
        //1.如果没用到第一个节点的值，则dp2[n]>dp1[n-1];
        //1.如果在dp1中用到了第一个节点的值，dp2可以保证一定没有用到，则比较dp1[n-1]与dp2[n]的值即可
        return Math.max(dp1[n-1],dp2[n]);
    }
}