[Leetcode笔记] 动态规划相关

前言

写题目写到了一些和动态规划相关的内容，所以在这里记录一下

LCR 089

题解思路

总的来说，就是用一个数组去存储当前的最优解，然后从0开始一路向上顺推过去，求得最后一位的最优解。

class Solution {
public:

    int rob(vector<int>& nums) {
        //然后从maxElement的左右一直找最大值 
        if(nums.empty()) return 0;
        int size = nums.size();
        if(size == 1) return nums[0];
        if(size == 2) return std::max(nums[0],nums[1]);
        vector<int> dp = vector<int>(size,0);
        dp[0] = nums[0];
        dp[1] = std::max(nums[0],nums[1]);
        for(int i = 2; i < size; i++){
            dp[i] = std::max(dp[i-1],dp[i-2] + nums[i]);
        }
        return dp[size-1];

    }
};

LCR 90

这道题和上述的089的区别就是这个题目中是需要考虑同时拿第一家和最后一家的情况，那我们这个动态规划可以稍微修改一下，实际上我们只需要修改一下边界条件即可：

转移方程仍然同上，边界条件修改为：

那么我们改一下遍历的过程：

	//提供一个从某个开头到某个结尾求最大值的方案
    int robRange(vector<int>& nums, int start, int end) {
        int first = nums[start], second = max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            int temp = second;
            second = max(first + nums[i], second);
            first = temp;
        }
        return second;
    }

得到这样一个方案之后，因为我们知道在这样一个偷东西问题上，两个房子之间不可能超过两个的差距，所以我们要么会偷头，要么会偷尾，所以只需要考虑两种情况，从0 - length 或者从 1 - length-1

    int rob(vector<int>& nums) {
        int length = nums.size();
        if (length == 1) {
            return nums[0];
        } else if (length == 2) {
            return max(nums[0], nums[1]);
        }
        return max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
    }