題意：

有一個(gè)k面的骰子，然后問你n個(gè)骰子朝上的面數(shù)字之和=s的方案；
思路：
dp[i][j] 代表 前 i 個(gè)骰子組成 j 有多少種方案；
顯然
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j - 2] + ... + dp[i - 1][j - k];

我們算 dp[i][j] 的時(shí)候，需要dp[i-1] 的前綴和已經(jīng)打出來了

我們求dp[i][j] 的時(shí)候，要求出 dp[i][j] 的前綴和，提供給求 i+1 的時(shí)候使用；

還有第二種方法：wonter

#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int>PII; const double eps=1e-5; const double pi=acos(-1.0); const int INF=0x3f3f3f3f; const int mod=100000007; const int N=15000+10; int n,k,s; int dp[N]; int sum[2][N];int main() {int T,cas=1;scanf("%d",&T);while(T--){scanf("%d%d%d",&n,&k,&s);memset(sum,0,sizeof(sum));memset(dp,0,sizeof(dp));for(int i=0;i<=s;i++)sum[0][i]=1;for(int i=1;i<=n;i++){sum[i&1][0]=0;for(int j=1;j<=s;++j){int l,r;l=max(0,j-k);r=j-1;if(l-1<0)dp[j]=sum[(i-1)&1][r];elsedp[j]=(sum[(i-1)&1][r]-sum[(i-1)&1][l-1]+mod)%mod;sum[i&1][j]=(sum[i&1][j-1]+dp[j])%mod;}}printf("Case %d: %d\n",cas++,dp[s]);}return 0; }/* 5 1 6 3 2 9 8 500 6 1000 800 800 10000 2 100 10 */

轉(zhuǎn)載于:https://www.cnblogs.com/keyboarder-zsq/p/6777493.html

總結(jié)

以上是生活随笔為你收集整理的lightoj1145 【DP优化求方案】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。