SRM401 Div2 500

問題

FerrersDiagramという、n=a1+a2+...+akとなるリストa1,a2,...,akでa1>a2>...>akとなるものを考える。さらにFIELD diagramというものを、nボックスが
□□...□□ ←fieldOrder個
□□...□
...
□□
□
と並んでいて、k行目の個数がak < fieldOrder-kであるようなFerrersDiagramとする。
整数fieldOrderが与えられるので、可能なFIELD diagramsの総数を返す。

考え方

dp．
2次元配列を用意して，問題(Example)の図のようにFerrersDiagramのマスで赤くなる個数を考えるdpを作る．
下から計算していって，その地点が何回赤くなるかを計算できる．

dp[][] = 0;
dp[fO-1][0] = 1;
for(int i=fO-2; i>=0; i--){
  for(int j=fO-i-1; j>=0; j--){
    dp[i][j] = dp[i][j+1] + (dp[i+1][0]-dp[i+1][j+1]+1);
  }
}

最終的にdp[0][0]が答えになる．

反省

実際に図を書いてみる．
前に計算した部分がそのまま使えそうならばその値でdpを立ててみる．