Link
Question
亮亮总共要跑 \(n\) 圈，可以分成多次，但是每次跑的圈数必须要比上一次跑的多，求跑完 \(n\) 圈的方案数
Solution
显然动态规划
定义 \(F[i][j]\) 表示一共跑了 \(i\) 圈，最后一次跑了 \(j\) 圈的方案数，转移方程就为
\[F[i][j]=\sum\limits_{k=1}^{j-1} F[i-j][k]
\]
答案就是
\[\sum\limits_{i=1}^N F[N][i]
\]
Code
#include<bits/stdc++.h>
using namespace std;
const int maxn=555;
typedef long long LL;
LL F[maxn][maxn];
int main(){
freopen("C.in","r",stdin);
int N;
cin>>N;
for(int i=1;i<=N;i++){
F[i][i]=1;
for(int j=1;j<i;j++){
for(int k=j-1;k>0;k--){
F[i][j]+=F[i-j][k];
}
}
}
LL ans=0;
for(int i=1;i<=N;i++)
ans+=F[N][i];
printf("%lld\n",ans-1);
return 0;
}