@[XH1111](/user/664087) 貌似思路有一点问题,这个 DP 要处理边界的,还有为什么结果要减去5
by Dws_t7760 @ 2023-10-02 08:49:14
@[t7760](/user/776962) emmm,打错了,-5是后面调的时候加的。
by XH1111 @ 2023-10-02 11:14:59
@[XH1111](/user/664087) 这题动态转移方程不是 $dp[i][j] = dp[i-1][j-1]+dp[max(i-j,0)][j]$ 吗
by Dws_t7760 @ 2023-10-02 11:35:43
@[t7760](/user/776962) 我没用动态转移方程吧。
by XH1111 @ 2023-10-02 11:36:41
@[XH1111](/user/664087) 啊这…… 那我再看看
by Dws_t7760 @ 2023-10-02 11:38:53
@[XH1111](/user/664087)
```
#include<bits/stdc++.h>
using namespace std;
long long n,k,f[10000][10000];
int main(){
cin>>n>>k;
if(k==1){
cout<<1;
return 0;
}
if(k==2){
cout<<n/2;
return 0;
}
for(int i=1;i<=n+1;i++) f[i][1]=1;
for(long long j=2;j<=k+1;j++)
for(long long i=2;i<=n+1;i++){
if(i==2&&j==2) f[i][j]=1;
else if(i==j) f[i][j]=1;
else if(i<j) f[i][j]=0;
else f[i][j]=f[i-j][j]+f[i-1][j-1];
}
cout<<f[n][k]<<endl;
return 0;
}
```
by Dws_t7760 @ 2023-10-02 11:42:24
@[t7760](/user/776962) 谢谢。
by XH1111 @ 2023-10-02 12:12:22