老薛主机做两个网站,电商平台页面设计,如何在网站上添加qq,广东公司响应式网站建设设计问题描述 一个正整数可以划分为多个正整数的和#xff0c;比如n3时#xff1a; 3#xff1b;1#xff0b;2#xff1b;1#xff0b;1#xff0b;1#xff1b; 共有三种划分方法。 给出一个正整数#xff0c;问有多少种划分方法。
输入格式 一个正整数n
…
问题描述 一个正整数可以划分为多个正整数的和比如n3时 312111 共有三种划分方法。 给出一个正整数问有多少种划分方法。
输入格式 一个正整数n
输出格式 一个正整数表示划分方案数
样例输入
3
样例输出
3
数据规模和约定 n100 #includeiostream
using namespace std;
int dp[110][110];//dp[i][j]用来表示数值i分成的数最高不超过j的情况数
int main()
{int n;cinn;for(int i0;in;i){dp[i][1]1;//拆出来的数不大于1的情况只有一种 dp[0][i]1;//0只有本身一种情况因为dp[0][N]dp[0][0],很玄学哈哈 }for(int i1;in;i)for(int j1;jn;j){if(ji){dp[i][j]dp[i][j-1]dp[i-j][j];/*dp[n][m]表示整数 n 的划分中每个数不大于 m 的划分数。则划分数可以分为两种情况:a. 划分中每个数都小于 m 相当于每个数不大于 m- 1, 故划分数为 dp[n][m-1].b. 划分中有一个数为 m. 那就在 n中减去 m , 剩下的就相当于把 n-m 进行划分 故划分数为 dp[n-m][m];*/}else{dp[i][j]dp[i][i];//如果允许拆出来的最大的数比这个数本身还大那么最大的数也就是这个数本身 }// coutdp[i][j]dp[i][j]endl;}coutdp[n][n]endl;}
另外感谢小伙伴给我的帮助
