蓝桥杯算法提高VIP-数的划分 （C++代码）

解题思路:

dp[i][j]为数值i分成的数最高不超过j的情况数。


注意事项:





参考代码:

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int dp[110][110];
int n;
int main()
{	
    cin>>n;
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++){
    	dp[0][i]=1;
    	dp[i][i]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(j<=i){
				dp[i][j]=dp[i][j-1]+dp[i-j][j];
			}
			else dp[i][j]=dp[i][i];
		}
	}
	cout<<dp[n][n];
    return 0;
}