プロジェクトオイラー問７６ - c21coterie @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2076

Problem 76 「和の数え上げ」 †

5は数の和として6通りに書くことができる:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

2つ以上の正整数の和としての100の表し方は何通りか.

解法
足す数を辞書順で考える。
例えば
5＝3+1+1だと３が一番大きな数で合計が5で左が３という情報以外組み合わせの計算にいらなくなる。
9を作るとき5＝3+1+1の左に4を足して9＝4+3+1+1、すると合計が9で左が4という情報だけ残しておけばよいｔ。
7＝6+1の左に2を足して9を作ろうとしても辞書順は壊れる。
これを考慮して動的計画法を立てると簡単に求まる。
Ｗｉｋｉの分割数のほうが解き方としては本格的だが、実装はできても原理がよくわからないので掲載していない。

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

int memo[101][101];

int main(){
	memset(memo,0,sizeof(memo));
 	for(int i=1;i<100;i++){
 		memo[i][i]=1;
	}
	for(int i=2;i<=100;i++){
		for(int j=1;j<i;j++){
			for(int k=1;k<=j;k++){
				memo[i][j]+=memo[i-j][k];
			}
 		}
}
 	int ans=0;
	for(int i=1;i<=99;i++){
		ans+=memo[100][i];
	}
	printf("%d\n",ans);
}