今日学习记录
1. 知道秘密的人数leetcode.2327
关键词：动态规划 前缀和 差分
问题分析：
- 一个人发现秘密后在 delay 天后会告诉另一个人,这个人过了 forget 时间后会忘记,求最后 n 天后,知道秘密的人数
核心思路
- 每个人会在 i+d 到 i+f 天里每天告诉一个人,i 天的每个人都会这样做,在 i+d<j<i+f 天里,nums[j]加上 nums[i],前面忘记的人就不管,到最后统计没有忘记的人,即 i+f-1>n
- 我们发现在 i+d 到 i+f 的期间都是在加一个相同的数,可以使用差分的方法,这个东西早在蓝桥杯的真题里就已经熟悉了,直接做
const int MOD = 1000000007;
int peopleAwareOfSecret(int n, int delay, int forget) {
vector<int> dp(n+1);
//初始化差分数组,以免1位置的数加到后面的位置去1了
//1为初始化值,不是题目中的数据
dp[1] = 1;
dp[2] = -1;
long long sum = 0;
//使用差分来进行范围的加法,但在这个基础上还要加上原有的数据
int now = 0;
for(int i = 1;i<=n;i++){
now = (now+dp[i])%MOD;//dp[i]为要加的数,now本身为原有数组中的数据
if (i >= n - forget + 1) {
sum += now;
}
//开始的地方加上now
if(i+delay<=n) dp[i+delay] = (dp[i+delay]+now)%MOD;
//结束的地方减去now
if(i+forget<=n) dp[i+forget] = (dp[i+forget]-now+MOD)%MOD;//做取模减法的时候要记得加一个MOD防止出现负数
}
return sum%MOD;
}- 对于刚刚那个范围里的都加同一个数,我们也可以直接求 j 该取值的范围来累加,求范围和使用前缀和,i+delay≤j≤i+forget−1 可以求出 j 的取值范围,得到 j−forget+1≤i≤j−delay,其实可以跳过这个思考过程,直接处理,因为前面已处理过后面的数据,所以放心加
const int MOD = 1000000007;
int peopleAwareOfSecret(int n, int delay, int forget) {
vector<int> arr(n+1);
//之前是i去找j,来更新i能到达的位置
//现在是看j,对于j而言,有哪些i能使其更新
arr[1] = 1;
int now = 0;
for(int j = 2;j<=n;j++){
//保证arr为前缀和数组,这里直接无脑范围加就行,不用刻意思考过程
now = (arr[max(j-delay,0)]-arr[max(j-forget,0)])%MOD;
arr[j] = (arr[j-1]+now)%MOD;
}
int ans = 0;
ans = arr[n]-arr[n-forget];
return (ans%MOD+MOD)%MOD;
}**最终代码：
const int MOD = 1000000007;
int peopleAwareOfSecret(int n, int delay, int forget) {
vector<int> dp(n+1);
dp[1] = 1;
long long sum = 0;
for(int i = 1;i<=n;i++){
if(i-1>=n-forget) sum += dp[i];
for(int j = i+delay;j<=min(i+forget-1,n);j++){
dp[j] = (dp[i]+dp[j])%MOD;
}
}
return sum%MOD;
}学到的点：
- 差分
- 前缀和