数的划分

• • Description--
  • 解题思路--
  • 代码--

Description–

高效进阶「基础算法」第1章 递推算法课堂过关 例题3

---

解题思路–

设f[i][j]为整数i分成j份的方案数

• 使j份中至少有一份为1（最后一份放1），则方案数为f[i-1][j-1]
• 使j份中一份1都没有，我们先将i-j分成j份，再在每一份中加1

---

代码–

#include <iostream>
#include <cstdio>
#define ll long long

using namespace std;

ll f[205][10];
int n, k;

int main()
{
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; ++i)
	  for (int j = 1; j <= min(i, k); ++j)
	  {
	  	  if (i == j || j == 1) f[i][j] = 1;
	  	  else f[i][j] = f[i - 1][j - 1] + f[i - j][j];
	  }
	printf("%lld", f[n][k]);
	
	return 0;
}