一、前言

此篇章主要整理一些关于线性dp的题目，很多题目其实都可以被挂上线性dp的标志，比如最熟悉的最长上升子序列啊，最长公共子序列啊等等，并且线性dp在自己写力扣周赛的题目的时候，真的会时不时出几道，然后刚好利用这些题目加上dp分析的方法，把题目好好写一写。

二、题目汇总

①力扣2369.检查数组是否存在有效的划分

(1)题目描述

(2)dp分析

状态转移方程：
f [ i ] = O r { f [ i − 2 ] , i ≥ 2 & & n u m [ i − 1 ] = n u m [ i − 2 ] f [ i − 3 ] , i > = 3 & & n u m [ i − 1 ] = n u m [ i − 1 ] = n u m [ i − 2 ] f [ i − 3 ] , i > = 3 & & n u m [ i − 1 ] − n u m [ i − 2 ] = n u m [ i − 2 ] − n u m [ i − 3 ] = = 1 f[i]=Or

f[i]=Or⎩ ⎨ ⎧​f[i−2],i≥2&&num[i−1]=num[i−2]f[i−3],i>=3&&num[i−1]=num[i−1]=num[i−2]f[i−3],i>=3&&num[i−1]−num[i−2]=num[i−2]−num[i−3]==1​
这个状态转移代表什么呢?

其实就是说，当我们选择第i个数的时候，如果在第$i-2$或者第$i-3$个数字前的划分都是正确的，那么我们选择i个数，满足三个条件中的时候，我们就可以有一个合理的划分。举一个例子，假设我们的数组是$[1,1,1,2,3]$,不难发现，对于1这个数字来说，划分有两种，既可以有前两个1组成一组，也可以是前3个1，因此$f(2),f(3)$都是True,而我们在i等于5的时候，我们此时就可以利用条件3，发现是递增的，那么我们在推导的时候，$f(5)||f(5-3)=True$,因此最终是可以成功划分的。

状态初始化

$f[0]=true,f[1]=false$

因为第0个划分不需要划分也是正确的，这个也是推出其他是否正确的一个必要条件。

最终结果: $f[n]$

时间复杂度: $O(N)$

(3)完整AC代码

class Solution {
public:
    bool validPartition(vector& nums) {
        int n = nums.size();
        vector f(n + 1, false);
        f[0] = true;

        for(int i = 2; i <= n; i ++ ) {
            if(nums[i - 1] == nums[i - 2]) f[i] = f[i] || f[i - 2];
            if(i >= 3) {
                if(nums[i - 1] == nums[i - 2] && nums[i - 2] == nums[i - 3])
                    f[i] = f[i] || f[i - 3];
                if(nums[i - 1] - nums[i - 2] == 1 && nums[i - 2] - nums[i - 3] == 1)
                    f[i] = f[i] || f[i - 3];
            }
        }

        return f[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

②力扣2370.最长理想子数组

(1)题目描述

(2)dp分析

状态转移方程:
f ( i , j ) = m a x { f ( i − 1 , j ) , 不选择第 i 个字符的情况 f ( i − 1 , [ m a x ( j − k , 0 ) , m i n ( j + k , 25 ) ] ) , 选择第 i 个字符的情况 f(i,j)=max

f(i,j)=max⎩ ⎨ ⎧​f(i−1,j),不选择第i个字符的情况f(i−1,[max(j−k,0),min(j+k,25)]),选择第i个字符的情况​
相关分析:

这个转移和最长上升子序列的那个dp非常的像，所以也就告诉我们，这个题目其实可以利用一维进行dp，当然下面的代码也会展现出二维的代码，就是二维的比较蛋疼，因为，每一层转移的时候，都需要把所有字符在上一层的状态迁移到本层，最终得到的结果才可以在最后一层里面推出来。

最终结果: $max(f[n][i],0\le i\le 25)$

时间复杂度: $O(n\ast (26+2\ast k))$

(3)完整AC代码

//二维代码
class Solution {
public:
    int longestIdealString(string s, int k) {
        int n = s.size();
        int f[100050][26];
        memset(f, 0, sizeof f);
        for(int i = 1; i <= n; i ++ ) {
            for(int j = 0; j < 26; j ++ ) f[i][j] = f[i - 1][j];
            int j = s[i - 1] - 'a';
            for(int p = max(j - k, 0); p <= min(j + k, 25); p ++ ) {
                f[i][j] = max(f[i][j], f[i - 1][p] + 1);
            } 
        }
        int maxn = 0;
        for(int i = 0; i < 26; i ++ ) {
            maxn = max(maxn, f[n][i]);
        }

        return maxn;
    }
};

//一维代码
class Solution {
public:
    int longestIdealString(string s, int k) {
        vector f(26, 0);
        for(auto c : s) {
            int j = c - 'a';
            f[j] = f[j] + 1;
            for(int i = max(0, j - k); i <= min(25, j + k); i ++ ) {
                if(i != j) f[j] = max(f[j], f[i] + 1);
            }
        }
        int maxn = 0;
        for(auto t : f) maxn = max(t, maxn);
        return maxn;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40