动态规划快速

动态规划

最大子数组和系列

53. 最大子数组和

我觉得这道题目的思想是： 走完这一生 如果我和你在一起会变得更好，那我们就在一起，否则我就丢下你。 我回顾我最光辉的时刻就是和不同人在一起，变得更好的最长连续时刻

——coolBoy

一切的一切都是从这个演化而来的：

int maxSubArray(vector<int>& nums) {
    int Max = nums[0];
    int pre = 0;
    for(auto &n : nums){
        pre = max(pre+n, n);
        Max = max(Max, pre);
    }
    return Max;
}

152. 乘积最大子数组

区别在于，多出一个变量来记录最小的乘积，因为最小的很可能突然变为最大的。

918. 环形子数组的最大和

非常巧妙，用同样的方法分别记录最小数组和和最大数组和。假设数组没有回环，那么最大数组就是max_sum；假设数组回环了，就进行total-min_sum

最后，还需要判断一下整个子数组都是负数的情况。

image.png

面试题 17.24. 最大子矩阵

使用top和bottom来遍历不同行数的矩阵。对于每一个固定行数的矩阵，可以采用前缀和的方式计算每列的和。之后转化为一维的最大子数组和问题。

363. 矩形区域不超过 K 的最大数值和

有点困难，之后再细看

打家劫舍问题

198. 打家劫舍

不算特别难，dp[i]设定为到达第i间房子之前能会获得的最大收益。

213. 打家劫舍 II

在上个问题的基础上，划分为抢第一间房子；不抢第一间房子。

740. 删除并获得点数

可以转换为打家劫舍问题

1388. 3n 块披萨

比较麻烦。题意可概括为，求一个3n大小的循环数组中长度为n的不连续子数组的最大和。需要用到打家劫舍II的思想，来处理循环数组问题。

将dp[i][j]定义为到第i个元素为止，选择j个元素的最大和。

其他单串dp[i]问题

32. 最长有效括号

413. 等差数列划分

91. 解码方法

132. 分割回文串 II