時間配置設定（dp）

一共有n個房子，每個房子裡面住着一個人，分别是庫特鴿鴿的n個迷妹。每天隻有k的空閑時間。

特别地，對于迷妹i（1<=i<=n），庫特鴿鴿花費的時間必須在0到a[i]（包括0和a[i]）之間。

求恰好花費k時間陪n個迷妹的方案數是多少。

（答案對1e9 + 7取餘）

第一行兩個整數n，k (1<=n<=100, 0<=k<=100000)

第二行n個整數 a[i] (0<=a[i]<=k)

輸出一個整數，代表方案數。

學長的題解：

題意分析：dp[i][j] 代表枚舉到了第 i 個迷妹，目前已經用掉了 j 時間的方案數

dp[i][j] = ∑(k = 1 to k = a[i]) dp[i-1][j-k]

這樣的的複雜度是 O(nk^2)，會 TLE，代碼如下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; 
const ll mod = 1e9 + 7;
int n,k;
int a[100005];
ll dp[105][100005]; 
int main() {
scanf("%d%d",&n,&k);
for(int i = 1;i<=n;i++) 
scanf("%d",&a[i]); dp[0][0] = 1;
for(int i = 1;i<=n;i++) 
{
for(int j = 0;j<=k;j++)
 {
	for(int m = 0;m<=min(a[i],j);m++) 
	{
	dp[i][j] = (dp[i][j] + dp[i-1][j-m]) % mod;
	 }
  }
}
printf("%lld\n",dp[n][k]);
return 0; 
}
           

怎麼優化?

我們發現在做 dp[i]這個次元的時候，dp[i-1]的東西是不會變的，而且對于每個 dp[i][j]有可 能算很多遍dp[i-1][j-k]，于是用字首和去優化，sum[j]代表dp[i-1][0] 到dp[i-1][j-1]的和。 時間複雜度 O(nk)

(當然 i 這一維可以滾掉，但這個題沒有卡空間)

代碼如下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
int n,k;
int a[100005];
ll dp[105][100005];
ll sum[100005]; 
int main() {
scanf("%d%d",&n,&k);
for(int i = 1;i<=n;i++) scanf("%d",&a[i]); 
for(int i = 0;i<=n;i++) dp[i][0] = 1; 
for(int i = 1;i<=n;i++) {
sum[0] = 0;
for(int j = 1;j<=k+1;j++) sum[j] = sum[j-1] + dp[i-1][j-1]; for(int j = 1;j<=k;j++)   dp[i][j] = (sum[j+1] - sum[max(0,j-a[i])] + mod) % mod;
} 
printf("%lld\n",dp[n][k]); 
return 0;
}