Leetcode-198-打家劫舍

Leecode-198-House Robber

思路：动态规划

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

简而言之：就是只能抢不相邻的两间屋子。

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

Solution：动态规划

• 动态规划的方程：dp[n] = MAX(dp[n-1],dp[n-2]+num[n-1])
• 因为不相邻的房间不可以闯入，所以当前位置n房屋可盗窃的最大值，要么就是n-1房屋可盗取的最大值，要么就是n-2房屋可盗窃的最大值加上当前房屋的值，二者之间取最大值
• 举例来说：1 号房间可盗窃最大值为 3 即为 dp[1]=3，2 号房间可盗窃最大值为 4 即为 dp[2]=4，3 号房间自身的值为 2 即为 num=2，那么 dp[3] = MAX( dp[2], dp[1] + num ) = MAX(4, 3+2) = 5，3 号房间可盗窃最大值为 5。

看一个例子：

1. 

2. 

3. 

4. 

Java

Solution :

class Solution{
    public int rob(int[] nums){
        int len = nums.length;
        if (len == 0){
            return 0;
        }

        // dp数组的长度是nums数组的长度加1
        // 因为dp[0] = 0
        int[] dp = new int[len + 1];

        // dp数组初始化
        dp[0] = 0;
        dp[1] = nums[0];

        // 状态转移方程
        for(int i = 2; i <= len; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]);
        }
        System.out.println(Arrays.toString(dp));
        // 返回dp数组的最后一个元素即为结果
        return dp[len];
    }
}

测试用例：

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

时间复杂度：O(n) -> 遍历了一遍数组

空间复杂度：O(n) - >额外使用了一个dp[n+1]长度的数组

Python

Solution :

打赏