[Project Euler 76]Counting summations

题目链接

https://projecteuler.net/problem=76

大意

将 \(100\) 拆分成至少两个数字的可行方案数是多少？

题解

如果做过放苹果这道题目的话，想必做这道题目是比较轻松的。

我们令 \(f_{i,j}\) 表示将 \(i\) 拆分成 \(j\) 份的方案数。

那么我们就可以得到这个递推方程：

$$f_{i,j}=f_{i-1,j-1}+f_{i-j,j}$$

边界条件是\(f_{i,1}=1,f_{i,i}=1\)。

#include <iostream>
#include <cstring>
#include <cmath>
#define MAXN 100
using namespace std;
int f[105][105],ans;
int main()
{
 for(int i=0;i<=MAXN;i++)
  f[i][1]=1,f[i][i]=1;
 for(int i=2;i<=MAXN;i++)
  for(int j=1;j<=i;j++)
   f[i][j]=f[i-1][j-1]+f[i-j][j];
 for(int i=2;i<=MAXN;i++)//应该至少被拆分成两个数
  ans+=f[MAXN][i];
 cout<<ans;
 return 0;
}