打家劫舍问题

发表于
本文字数： 991 阅读时长 ≈ 1 分钟

LeetCode每日一题，198.House Robber

先看题目描述

题目大意是输入的数组代表一个个房子里存的金钱数目，我们是个劫匪，不能抢相邻房子里的钱，最多能抢到钱的数目是多少。虽然这是道简单题，但一开始想了好久没想出来，最后看题解才做出来，用动态规划就可以很轻松的解决

算法和思路

  • 动态规划

  • 动态规划方程: dp[0] = 0，dp[1] = nums[0]，dp[i] = Max(dp[i - 1], dp[i - 2] + nums[i - 1])（i >= 2）

  • 由于不可以抢劫相邻的房屋，所以在第 n 个房子时盗窃到的最大值，要么就是 n - 1房子时可盗窃的最大值，要么就是 n - 2 房子盗窃到的最大值加上第 n 个房子里盗窃到的钱，在这两者中取较大那个赋值给 dp[n] 即可

  • 例: 房子里的钱是[1, 2, 3, 1]，dp[0] = 0，dp[1] = nums[0] = 1，dp[2] = Max(dp[1], dp[0] + nums[1]) = Max(1, 0 + 2) = 2，dp[3] = Max(dp[2], dp[1] + nums[2]) = Max(2, 1 + 3) = 4，dp[4] = Max(dp[3], dp[2] + nums[3]) = Max(4, 2 + 1) = 4，故最后返回 dp[4] 即得到最终结果

实现源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.*;

class Solution {
    public int rob(int[] nums) {
        int[] dp = new int[nums.length + 1];
        dp[0] = 0;
        if (nums.length == 0) return 0;
        dp[1] = nums[0];
        for(int i = 2; i <= nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return dp[nums.length];
    }
}