一、前言
此篇章主要整理一些关于线性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 \begin{cases} f[i-2], i\ge2\&\&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 \end{cases}
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-2 i−2或者第 i − 3 i-3 i−3个数字前的划分都是正确的，那么我们选择i个数，满足三个条件中的时候，我们就可以有一个合理的划分。举一个例子，假设我们的数组是 [ 1 , 1 , 1 , 2 , 3 ] [1,1,1,2,3] [1,1,1,2,3],不难发现，对于1这个数字来说，划分有两种，既可以有前两个1组成一组，也可以是前3个1，因此 f ( 2 ) , f ( 3 ) f(2),f(3) f(2),f(3)都是True,而我们在i等于5的时候，我们此时就可以利用条件3，发现是递增的，那么我们在推导的时候， f ( 5 ) ∣ ∣ f ( 5 − 3 ) = T r u e f(5) || f(5-3)=True f(5)∣∣f(5−3)=True,因此最终是可以成功划分的。
状态初始化
f [ 0 ] = t r u e , f [ 1 ] = f a l s e f[0]=true, f[1]=false f[0]=true,f[1]=false
因为第0个划分不需要划分也是正确的，这个也是推出其他是否正确的一个必要条件。
最终结果:
f
[
n
]
f[n]
f[n]
时间复杂度:
O
(
N
)
O(N)
O(N)
(3)完整AC代码
class Solution {
public:
bool validPartition(vector<int>& nums) {
int n = nums.size();
vector<bool> 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];
}
};
②力扣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 \begin{cases} f(i-1,j),不选择第i个字符的情况 \\\\ f(i-1,[max(j-k,0),min(j+k,25)]),选择第i个字符的情况 \end{cases}
f(i,j)=max⎩
⎨
⎧f(i−1,j),不选择第i个字符的情况f(i−1,[max(j−k,0),min(j+k,25)]),选择第i个字符的情况
相关分析:
这个转移和最长上升子序列的那个dp非常的像，所以也就告诉我们，这个题目其实可以利用一维进行dp，当然下面的代码也会展现出二维的代码，就是二维的比较蛋疼，因为，每一层转移的时候，都需要把所有字符在上一层的状态迁移到本层，最终得到的结果才可以在最后一层里面推出来。
最终结果:
m
a
x
(
f
[
n
]
[
i
]
,
0
≤
i
≤
25
)
max(f[n][i], 0\leq i \leq 25)
max(f[n][i],0≤i≤25)文章来源：https://www.toymoban.com/news/detail-401521.html
时间复杂度:
O
(
n
∗
(
26
+
2
∗
k
)
)
O(n*(26 + 2 * k))
O(n∗(26+2∗k))文章来源地址https://www.toymoban.com/news/detail-401521.html
(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<int> 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;
}
};
到了这里，关于线性DP题目汇总(持续更新)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
