※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「プロジェクトオイラー問76」の編集履歴(バックアップ)一覧に戻る
プロジェクトオイラー問76」を以下のとおり復元します。
解法
足す数を辞書順で考える。
例えば
5=3+1+1だと3が一番大きな数で合計が5で左が3という情報以外組み合わせの計算にいらなくなる。
9を作るとき5=3+1+1の左に4を足して9=4+3+1+1、すると合計が9で左が4という情報だけ残しておけばよいt。
7=6+1の左に2を足して9を作ろうとしても辞書順は壊れる。
これを考慮して動的計画法を立てると簡単に求まる。
Wikiの分割数のほうが解き方としては本格的だが、実装はできても原理がよくわからないので掲載していない。



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

復元してよろしいですか?