跳转至

打家劫舍 II⚓︎

Leetcode题目链接

描述⚓︎

详见中文题目链接。

解答⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
private:
    int n;
    int _rob(vector<int>& nums, int start, int end) {
        if (start == end) return nums[start];
        vector<int> dp(n, 0);
        dp[start] = nums[start];
        dp[start + 1] = max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            dp[i] = max(nums[i] + dp[i - 2], dp[i - 1]);
        }
        return dp[end];
    }
public:
    int rob(vector<int>& nums) {
        n = nums.size();
        if (nums.size() == 1) return nums[0];
        int res1 = _rob(nums, 0, n - 2);
        int res2 = _rob(nums, 1, n - 1);
        return max(res1, res2);
    }
};