0%

leetcode周赛压轴专题

最近周赛的压轴题都是dp,总结一下

leetcode 1425 带限制的子序列和

给你一个整数数组 nums 和一个整数 k ,请你返回 非空 子序列元素和的最大值,子序列需要满足:子序列中每两个 相邻 的整数 nums[i] 和 nums[j] ,它们在原数组中的下标 i 和 j 满足 i < j 且 j - i <= k 。

数组的子序列定义为:将数组中的若干个数字删除(可以删除 0 个数字),剩下的数字按照原本的顺序排布。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
示例 1

输入:nums = [10,2,-10,5,20], k = 2
输出:37
解释:子序列为 [10, 2, 5, 20] 。
示例 2

输入:nums = [-1,-2,-3], k = 1
输出:-1
解释:子序列必须是非空的,所以我们选择最大的数字。
示例 3

输入:nums = [10,-2,-10,-5,20], k = 2
输出:23
解释:子序列为 [10, -2, -5, 20] 。

$1 <= k <= nums.length <= 10^5$
$-10^4 <= nums[i] <= 10^4$

思路:朴素dp做法就是$dp[i]=nums[i]+max(0,dp[i-k],dp[i-k+1],…dp[i-1)$,dp[i]表示包含nums[i]的满足条件的子序列的最大和,复杂度是$n^2$的,可以使用滑动窗口最大值优化,维护一个大小为k的滑动窗口,有状态转移方程:
$dp[i]=max(nums[i],dp[q.front()] + nums[i])$其中dp[q.front()]是滑动窗口中的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int constrainedSubsetSum(vector<int>& nums, int k) {
int n = nums.size(),res;
vector<int>dp(n);
deque<int>q;
q.push_back(0);
res=dp[0]=nums[0];
for(int i=1;i<n;i++){
dp[i]=max(nums[i],dp[q.front()] + nums[i]);
res = max(res,dp[i]);
while(!q.empty() && q.front() <= i-k)q.pop_front();
while(!q.empty() && dp[q.back()] <= dp[i])q.pop_back();
q.push_back(i);
}
return res;
}
};

leetcode 1420 生成数组

给你三个整数 n、m 和 k 。下图描述的算法用于找出正整数数组中最大的元素。

请你生成一个具有下述属性的数组 arr :

arr 中有 n 个整数。

  • 1 <= arr[i] <= m 其中 (0 <= i < n) 。
  • 将上面提到的算法应用于 arr ,search_cost 的值等于 k 。
  • 返回上述条件下生成数组 arr 的 方法数 ,由于答案可能会很大,所以 必须 对 $10^9 + 7$ 取余。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
示例 1

输入:n = 2, m = 3, k = 1
输出:6
解释:可能的数组分别为 [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]
示例 2

输入:n = 5, m = 2, k = 3
输出:0
解释:没有数组可以满足上述条件
示例 3

输入:n = 9, m = 1, k = 1
输出:1
解释:可能的数组只有 [1, 1, 1, 1, 1, 1, 1, 1, 1]
示例 4

输入:n = 50, m = 100, k = 25
输出:34549172
解释:不要忘了对 1000000007 取余
示例 5

输入:n = 37, m = 17, k = 7
输出:418930126

1 <= n <= 50
1 <= m <= 100
0 <= k <= n

思路:
方法一:朴素dp,dp[i][j][k]表示构建i位数用到的最大数为j的消耗为k的方案数。按照用到的数来进行状态划分。如果上一轮已经用了最大数j,消耗为k,那么这一轮不会生成更大的数,此时是从上一轮中消耗k转移来的,本轮可选共j种可能(1..j),如果上一轮没用最大数j(即用到j-1),消耗为k,那么当前轮使用最大数j会让消耗加1,所以是从上一轮中消耗k-1转移来的。所以有转移方程:
$dp[i][j][k] = dp[i-1][j][k]* j + sum(dp[i-1][1..j-1][k-1])$
时间复杂度: $O(km^2n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
const int mod = 1000000000 + 7;
int dp[51][101][51];
int numOfArrays(int N, int M, int K) {
for(int i=1;i<=M;i++)dp[1][i][1]=1;
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
for(int k=1;k<=K;k++){
dp[i][j][k] = (dp[i][j][k] + (long)dp[i-1][j][k] * j)%mod;
for(int u=1;u<j;u++){
dp[i][j][k]=(dp[i][j][k] + dp[i-1][u][k-1])%mod;
}
}
}
}
int res=0;
for(int i=1;i<=M;i++)res=(res+dp[N][i][K])%mod;
return res;
}
};

方法二:使用前缀和优化,可以发现其实对于如果从k-1转移过来,加上的方案数是连续的和,所以可以用前缀和来优化。时间复杂度:$O(kmn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
const int mod = 1000000000 + 7;
int dp[51][101][51];
int pre[51][101][51];
int numOfArrays(int N, int M, int K) {
int res=0;
for(int i=1;i<=M;i++){
dp[1][i][1]=1;
pre[1][i][1] = pre[1][i-1][1]+1;
}
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
for(int k=1;k<=K;k++){
dp[i][j][k] = (dp[i][j][k] + (long)dp[i-1][j][k]* j + pre[i-1][j-1][k-1])%mod;
pre[i][j][k] = (dp[i][j][k] + pre[i][j-1][k])%mod;
}
if(i==N)res=(dp[N][j][K]+res)%mod;
}
}
return res;
}
};

leetcode 1416 恢复数组

某个程序本来应该输出一个整数数组。但是这个程序忘记输出空格了以致输出了一个数字字符串,我们所知道的信息只有:数组中所有整数都在 [1, k] 之间,且数组中的数字都没有前导 0 。

给你字符串 s 和整数 k 。可能会有多种不同的数组恢复结果。

按照上述程序,请你返回所有可能输出字符串 s 的数组方案数。

由于数组方案数可能会很大,请你返回它对 $10^9 + 7$ 取余 后的结果。

1
2
3
4
5
6
7
8
9
10
11
12
输入:s = "1317", k = 2000
输出:8
解释:可行的数组方案为 [1317],[131,7],[13,17],[1,317],[13,1,7],[1,31,7],[1,3,17],[1,3,1,7]
示例 4

输入:s = "2020", k = 30
输出:1
解释:唯一可能的数组方案是 [20,20] 。 [2020] 不是可行的数组方案,原因是 2020 > 30 。 [2,020] 也不是可行的数组方案,因为 020 含有前导 0
示例 5

输入:s = "1234567890", k = 90
输出:34
  1. $1 <= s.length <= 10^5.$
  2. s 只包含数字且不包含前导 0 。
  3. $1 <= k <= 10^9.$

思路:(动态规划) $O(nlog_{10}k)$
设状态 f(i) 表示前 i 个数字的合法划分方案,这里的下标从 1 开始。
初始值 f(0)=1,其余为 0。
转移时,如果子串 [j + 1, i] 转换为数字后在范围 [1, k] 中,则转移 f(i)=f(i)+f(j)。
最终答案为 f(n)。
时间复杂度
状态数为 O(n),转移时,j 不会小于 $i−log_{10}k−1$,所以总时间复杂度为 $O(nlog_{10}k)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
const int mod = 1000000000+7;
int numberOfArrays(string s, int k) {
int n=s.size();
vector<int>dp(n+1);
dp[0]=1;
for(int i=1;i<=n;i++){
long cur=0,p=1;
for(int j=i-1;j>=0&&p<=1e9;j--,p*=10){
cur += (s[j]-'0')*p;
if(cur<=k && s[j]!='0')dp[i]=(dp[i] + dp[j])%mod;
}
}
return dp[n];
}
};