プロジェクトオイラー 76. 〜Counting Summations〜

No.76 Counting Summations

問題.

5は正整数の和として:\begin{align*}
&4+1\\
&3+2\\
&3+1+1\\
&2+2+1\\
&2+1+1+1\\
&1+1+1+1+1
\end{align*}の6通りに書ける．では，100は正整数の和として何通りに書けるか．

考え方とプログラム例.(c++)

動的計画法です．先に問題77. の記事を書きましたが，考え方はほとんど同じです．

整数を以下の正整数の和として表す方法の個数を通りとすると，以下の漸化式が成り立つ：

の場合について，整数を使わない場合が通り，整数を使う場合が通りです．

以下がプログラム例です．メモ化再帰？を使ってみました．

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

vector<vector<int>> F(101, vector<int>(100, 0));

ll f(int n, int k){
	ll ret = 0;
	if(F[n][k] > 0)
		return F[n][k];
	if(n - k >= 0)
		ret += f(n-k, k);
	ret += f(n, k-1);
	F[n][k] = ret;
	return ret;
}

int main(){
	for(int n = 0; n <= 100; n++)	F[n][1] = 1;
	cout << f(100, 99) << endl;
	return 0;
}