计蒜客-简单的划分数 动态规划

题目链接 https://www.jisuanke.com/course/709/36576

题解： 典型的整数划分问题 ，  建议参考母函数（整数划分）的资料将几种比较典型的整数划分问题搞懂

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll dp[84][84];

int main() {
	for(int i = 1;i <= 80;i++) {
		dp[i][1] = 1;
	}
	
	for(int i = 1;i <= 80;i++)
		for(int j = 2;j <= 80;j++) {						
			if(j > i) dp[i][j] = dp[i][i];
			else if(j == i) dp[i][i] = 1+dp[i][i-1];
			else dp[i][j] = dp[i][j-1] + dp[i-j][j];			
		}
	
	printf("%lld\n",dp[80][80]);
	
			
	return 0;
}