[数据结构与算法]动态规划经典题目：打家劫舍

动态规划经典题目：打家劫舍

一、198. 打家劫舍

1.1 解法一：动态规划，二维DP

    public int rob(int[] nums) {
        int[][] dp = new int[nums.length][2];
        // dp[i][0] 不偷
        // dp[i][1] 偷
        dp[0][0] = 0;
        dp[0][1] = nums[0];
        for (int i=1; i<nums.length; i++) {
            // 当前房子偷的情况
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);
            // 当前房子不偷的情况
            dp[i][1] = dp[i-1][0] + nums[i];
        }
        return Math.max(dp[nums.length-1][0], dp[nums.length-1][1]);
    }

1.2 解法二：动态规划，一维DP

    public int rob(int[] nums) {
        int n = nums.length;
        if (n<2) return nums[0]; 
        int[] dp = new int[n];
        // dp[i] 为第i个位置能够得到的最大值
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i=2; i<n; i++) {
            // 第i个房子偷，或者不偷
            dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2]);
        }
        return dp[n-1];
    }

1.3 解法三：动态规划，使用三个变量（进一步简化）

    public int rob(int[] nums) {
        // 前一个值
        int pre = 0;
        // 当前值
        int now = 0;
        for (int i=0; i<nums.length; i++) {
            // dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2]);
            int t = now;
            now = Math.max(now, nums[i] + pre);
            pre = t;
        }
        return now;
    }

二、213. 打家劫舍 II

将这个问题转化成第一个问题

    public int rob(int[] nums) {
        if (nums.length==1) return nums[0];
        // 转换成打家劫舍I: 第一个房子不偷，或者最后一个房子不偷
        return Math.max(solve(0, nums.length-2, nums) , solve(1, nums.length-1, nums));
    }

    private int solve(int low, int hi, int[] nums) {
        int pre=0;
        int now=0;
        for (int i=low; i<=hi; i++) {
            int t = now;
            now = Math.max(now, nums[i]+pre);
            pre = t;
        }
        return now;
    }