LeetCode刷题--- 打家劫舍 II

• 状态显示

• 状态转移方程

dp[i]=max(dp[i?2]+nums[i],dp[i?1]).

• 初始化（防止填表时不越界）

dp1[left] = nums[left];

• 填表顺序

根据「状态转移?程」得「从左往右，两个表?起填」。

• 返回值

?return max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));

代码实现

• 时间复杂度：O(n)，其中?n?是数组长度。需要对数组遍历两次，计算可以偷窃到的最高总金额。

• 空间复杂度：O(n)。

class Solution 
{
public:
    int rob(vector<int>& nums)
    {
        int n = nums.size();
        // 两种情况下的最?值
        return max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));
    }

    int rob1(vector<int>& nums, int left, int right)
    {
        if(left > right) 
        {
            return 0;
        }
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回结果
        int n = nums.size();
        vector<int> dp1(n);
        auto dp2 = dp1;

        dp1[left] = nums[left]; // 初始化
        for(int i = left + 1; i <= right; i++)
        {
            dp1[i] = dp2[i - 1] + nums[i];
            dp2[i] = max(dp1[i - 1], dp2[i - 1]);
        }
        return max(dp1[right], dp2[right]);
    }
};