一道 DP 前缀和优化好题。
题目分析
首先，朴素 DP 非常好想。可以从后向前考虑，设 \(f_i\) 表示从第 \(i\) 个补品开始的摄取方法数。
摄取一个补品：\(f_i = f_{i+1}\)
摄取两个补品：\(f_i = f_{i+2}\)
以此类推。
则转移方程为：
\[f_i = f_{i+1} + f_{i+2} + \dots + f_{j}
\]
这里的 \(j\) 指 \(i\) 向后最远能取到的保证不重复的数，这一步可以用 unordered_map 判重。
朴素 DP 参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100005,mod = 1e9+7;
int n,m,a[N],dp[N];
int main()
{
cin >> n >> m;
for (int i = 1;i <= n;i++) cin >> a[i];
dp[n+1] = 1;
for (int i = n;i >= 1;i--)
{
dp[i] = dp[i+1];
unordered_map<int,bool> mp;//map判重
mp[a[i]] = 1;
for (int j = i+1;j <= n;j++)
{
if (mp[a[j]]) break;
dp[i] += dp[j+1] % mod,dp[i] %= mod;
mp[a[j]] = 1;
}
}
cout << dp[1] << endl;
return 0;
}
DP 优化
朴素 DP 时间复杂度 \(O(n^2)\)，于是考虑优化。
朴素 DP 是 \(O(n)\) 枚举查找 \(j\) 的位置，那么可以预处理每个 \(i\) 对应 \(j\) 的位置，再通过前缀和求出 \(f_{i+1} + f_{i+2} + \dots + f_{j}\) 的值，就可以优化状态转移时间复杂度为 \(O(1)\)。
最终复杂度为 \(O(n)\)。
预处理的方法
怎么求出每个 \(i\) 对应的 \(j\) 的位置呢？我们发现 \(j\) 的位置是随着 \(i\) 单调递增的，因为 \(i-1\) 对应的 \(j\) 对于 \(i\) 来说肯定也是可行的。
所以很容易能想到使用双指针算法，时间复杂度 \(O(n)\)。
具体实现见代码。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100005,mod = 1e9+7;
int n,m,a[N];
int dp[N],bk[N],sum[N];
unordered_map<int,int > mp;
int main()
{
cin >> n >> m;
for (int i = 1;i <= n;i++) cin >> a[i];
for (int i = 1,j = i;i <= n;i++) //双指针算法
{
while (j <= n && !mp[a[j]]) mp[a[j]]++,j++;
bk[i] = j-1; //存储每个i最远能走到的数
mp[a[i]]--;
}
dp[n+1] = sum[n+1] = 1;
for (int i = n;i >= 1;i--)
{
//dp[i] = dp[i+1] + dp[i+2] + ... + dp[bk[i] + 1]
dp[i] =( sum[i+1]-sum[bk[i] + 2] + mod) % mod;
sum[i] = (sum[i+1] + dp[i]) % mod;
}
cout << dp[1] << endl;
return 0;
}