J - Staircases （递推&数的划分）

J - Staircases （递推&数的划分）

题意：求有多少种不同数之和为n的方案。(划分个数大于1）

思路：

AC代码：

#include<cstdio>
#include<cstring>
using namespace std;
const int N=5e2+5;
typedef long long ll;
ll dp[N][N];
int main(){
	int n;
	while(~scanf("%d",&n)){
		memset(dp,0,sizeof dp);
		for(int i=1;i<=n;i++) dp[i][i]=1;
		for(int i=2;i<=n;i++)
			for(int j=i-1;j>=1;j--)
				dp[i][j]=dp[i-j][j+1]+dp[i][j+1];
		printf("%lld\n",dp[n][1]-1);
	}
	return 0;
} 

附上一维代码（PS:不太理解，貌似类似于背包的降维）

#include<cstdio>
#include<cstring>
using namespace std;
const int N=5e2+5;
typedef long long ll;
ll dp[N];
int main(){
	int n;
	while(~scanf("%d",&n)){
		memset(dp,0,sizeof dp);
		dp[0]=1;
		for(int i=1;i<=n;i++)
			for(int j=n;j>=i;j--)
				dp[j]+=dp[j-i];
		printf("%lld\n",dp[n]-1);
	}
	return 0;	
}