【动态规划】（一）线性动态规划之单串问题

线性动态规划的主要特点是状态的推导是按照问题规模 i 从小到大依次推过去的，较大规模的问题的解依赖较小规模的问题的解。这里问题规模为 i 的含义是考虑前 i 个元素 [0..i] 时问题的解。

大规模问题的状态只与较小规模的问题有关，而问题规模完全用一个变量 i 表示，i 的大小表示了问题规模的大小，因此从小到大推 i 直至推到 n，就得到了大规模问题的解，这就是线性动态规划的过程。

按照问题的输入格式，线性动态规划解决的问题主要是单串，双串，矩阵上的问题，因为在单串，双串，矩阵上问题规模可以完全用位置表示，并且位置的大小就是问题规模的大小，因此从前往后推位置就相当于从小到大推问题规模。

单串问题

单串 dp[i] 是线性动态规划最简单的一类问题，输入是一个串，状态一般定义为 dp[i] := 考虑[0..i]上，原问题的解，其中考虑[0..i]上，原问题的解又可以分为两大类，即我们要考虑[0..i]上所有子问题的解（考虑O(n)个子问题的解），还是只考虑考虑[0..i]上常数个子问题的解（考虑O(1)个子问题的解），一般只考虑常数个子问题的解就是考虑 dp[i-1] 或（和）dp[i-2]。单串问题基本上可以分为以下几大类。

1 最长递增子序列（LIS问题）

这是最经典的线性动态规划问题，也是最能体现线性动态规划思想的问题之一。

问题描述：

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

我们用$f(i)$表示以nums[i]结尾的子数组的LIS长度，因为子序列需要上升，因此以 nums[i] 结尾的子序列中，nums[i] 之前的数字一定要比 nums[i] 小才行，因此目标就是先找到以此前比 nums[i] 小的各个元素，然后每个所选元素对应一个以它们结尾的最长子序列，从这些子序列中选择最长的，其长度加 1 就是当前的问题的结果。如果此前没有比 nums[i] 小的数字，则当前问题的结果就是 1 。于是可以写出状态转移方程：
$$
f(i)=\left{
\begin{aligned}
max(f(i),f(j))+1 & , & nums[i]>nums[j], \
1 & , & nums[i]<=nums[j].
\end{aligned}
\right.
$$
其中$j < i$，显然求解$f(i)$需要遍历所有$f(j)$，因此我们要考虑 O(n) 个子问题的解。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(),1);
        int ans = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(nums[j] < nums[i])
                {
                    dp[i] = max(dp[i],dp[j] + 1);
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

LIS问题及其变体问题：

最长递增子序列
最长递增子序列的个数：除了维护记录长度的dp数组外，还要维护一个记录子序列个数的cnt数组
俄罗斯套娃信封问题
最大整除子集：动态规划过程类似于最长上升子序列，难点在于还原出子集的所有元素

2 最大子数组和

另一个经典单串问题

问题描述：

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

同样的思路，我们用 dp[i] 表示以nums[i]结尾的最大子数组和，因为状态的推导是按照 i 从 0 到 n - 1 按顺序推的，推到 dp[i]，时，dp[i - 1], …, dp[0] 已经计算完。因为子数组是连续的，所以子问题 dp[i] 其实只与子问题 dp[i - 1] 有关。如果 [0..i-1] 上以 nums[i-1] 结尾的最大子数组和(缓存在 dp[i-1] )为非负数，则以 nums[i] 结尾的最大子数组和就在 dp[i-1] 的基础上加上 nums[i] 就是 dp[i] 的结果否则以 i 结尾的子数组就不要 i-1 及之前的数，因为选了的话子数组的和只会更小。因此可以写出状态转移方程：

1	dp[i] = nums[i] + max(dp[i - 1], 0)

显然这个问题中，我们只要考虑O(1)个子问题的解，因此也没有必要维护 dp 数组了，运用滚动数组的思想，只要记录下来 dp[i-1] 就可以了。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int fi = 0;
        int res = INT_MIN;
        for(int i = 0; i<nums.size();i++)
        {
            fi = max(fi + nums[i], nums[i]);
            res = max(res,fi);
        }
        return res;
    }
};

最大子数组和及其变体问题：

3 打家劫舍问题

打家劫舍类似于最大子数组和，但这里的子数组不能连续，也就是不相邻子序列的最大和问题。

问题描述：

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

问题的关键在于我们如果偷了第 i 个房间，那么就不能偷第 i-1 个房间，所以 dp[i] 表示到第 i 个房间为止的最大金额，这个最大金额的取值有两种情况，如果我们不偷第 i 个房间，那么 dp[i] = dp[i-1]；如果我们偷第 i 个房间，那么 dp[i] = dp[i-2] + num[i]。

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() <= 2)
        {
            return *max_element(nums.begin(),nums.end());
        }
        int dp1 = nums[0];              //屋子能偷盗的最大金额
        int dp2 = max(dp1,nums[1]);     //前一间屋子能偷到的最大金额
        int ans = max(dp1, dp2);
        for(int i = 2; i < nums.size(); i++)
        {
            ans = max(dp1 + nums[i], dp2);
            dp1 = dp2;
            dp2 = ans;
        }
        return ans;
    }
};

打家劫舍及其变体问题：

打家劫舍
打家劫舍 II：数组变成了环形，也就是偷了第1个房间就不能偷最后一个房间，在区间 [0, nums.size()-1] 和 [1, nums.size()] 上应用两次打家劫舍的算法即可
删除并获得点数：难点在于怎么转换成打家劫舍问题
3n 块披萨：难点在于动态规划状态的定义，因为一定有 3n 个数，我们最多只能拿其中 n 个数字，所以相当于打家劫舍中我们只能偷 3n 个房间中的 n 个

4 需要记录两个位置的问题

有一些单串问题在涉及状态时需要考虑相邻两个元素的情况，因为只考虑最后一个的话无法对状态描述清楚，例如：

最长的斐波那契子序列的长度：$dp[i][j]$表示以 $j, i$ 结尾的最长斐波那契子序列长度，转移时在 [0..j] 中找满足条件的 k
最长等差数列：同上，但是两道题的具体实现细节稍有不同

5 其他没有显式给定数组的线性动态规划问题

线性 DP 还有一些问题没有显式的数组，字符串等。此类问题一般没有什么固定的模式，只能通过多做题来积累。

最长有效括号：这道题最容易想到的是用栈，但其实算法过程比较难做对，用动态规划更简单，但对于状态转移的过程比较难想到
等差数列划分：最长等差数列的简单版本，给定的数组是严格递增或递减的，处理起来会简单很多
解码方法：关键在于有效数字只有可能是一位或者两位，因此对于任何一个数字，要么本身一位进行编码，要么和前一位组成两位数字进行编码
分割回文串：主要考察的是深搜回溯的方法，但是使用动态规划对字符串预处理可以在O(1)时间内判断回文子串
分割回文串 II：dp[i] 表示以 s[i] 结尾的字符串的最小分割次数，状态转移时如果 s[i] 能与前面的某个位置 j 组成回文子串 s[j…i]，那么dp[i] = dp[j] + 1，遍历所有满足条件的 j < i ，dp[i]取这些值里面的最小值，判断回文子串 s[j…i] 时同样可以用分割回文串中的动态规划方法，所以本题进行了两次动态规划，较为复杂。
两个字符串的删除操作：转化成LCS问题可以很简单的解决，但还可以用更符合题意的状态定义$dp[i][j]$
比特位计数：比较简单