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

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だと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);
}