project euler 76

問題

数字の5は，以下のように6種類の数字の和で表現できる．
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
同様にして，数字の100は，2つ以上の和で表現すると何種類あるか．

考え方

上の分解を見てわかる通り，各和は，i番目の数字がi-1番目の数字以下であるように分解される．
なので，数字aを超えないようにbを分解する組み合わせの数を計算するcalc(a,b)を考える．

• a==1の場合はbが何であれ1+1+...としか表現できないので1を返す．
• b==1の場合はaが何であれ1としか表現できないので1を返す．
• a>=bの場合は，bをそのまま分解すればよいので，
  • 1+calc(b-1,1)+...+calc(1,b-1)
    • ただし，最初の1は分解せずにそのまま残した場合を表す．
• a
  • calc(a,b-a)+calc(a-1,b-a+1)+...+calc(1,b-1)

答えは，100を2つ以上の和で表現する場合なので，
calc(99,1)+calc(98,2)+...+calc(1,99)
が答えになる．