プロジェクトオイラー問76 - sinapusu2002 @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2076
Problem 76 「和の数え上げ」 †
分割数に関する問題。

解法
書くだけならWikiの分割数の公式を使えばいいのですがWikiにある式の理屈が理解できず。
動的計画法で計算する方法はパッと思いつけますし、理屈も単純ですのでこれで計算してみました。

#include<stdio.h>
#include<string.h>

const int LIMIT=100;
__int64 dp[LIMIT+1][LIMIT+1];

int main(){
	memset(dp,0,sizeof(dp));
	dp[0][0]=1;
	for(int i=0;i<LIMIT;i++){
		for(int j=0;j<LIMIT;j++){
			for(int k=j;i+k<=LIMIT;k++){
				if(k==0)continue;
				dp[i+k][k]+=dp[i][j];
 			}
		}
	}
	__int64 ans=0;
 	for(int j=1;j<LIMIT;j++){
		ans+=dp[LIMIT][j];
	}
	printf("%lld",ans);
}