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;	
}