蟻本の分割数の問題を整理
目的
僕には何を言っているのかさっぱりだったので、他の方の解説を見ながら整理して理解する
分割数
nをm個以下に順序を区別せずに分割する方法の総数
m=nのとき特にnの分割数と呼ぶ
問題の漸化式
dp[i][j] = dp[i][j-i] + dp[i-1][j]
このdpのメモは、jをi分割したときの総数(dp[i][j] = jをi分割したときの総数)
まずjをi分割するとなったときにi個のものが自動的に最低1の数としてまず確定する
例えば5を3分割した場合、次の2パターン
- 3, 1, 1
- 2, 2, 1
7を4分割した場合、次の3パターン
- 4, 1, 1, 1
- 3, 2, 1, 1
- 2, 2, 2, 1
このときどう分割したところで、それぞれの数は1より下にならない
つまりそれぞれの数から1を引いた数であるj-iの、順序を区別しない並べ方と考えることができる(このときは0を含むので注意)
イメージ的にはi個分の箱を用意して、j-i個のボールを重複のパターンがでないように入れる感じ
上記5を3分割した場合では
- 2, 0, 0
- 1, 1, 0
7を4分割した場合では
- 3, 0, 0, 0
- 2, 1, 0, 0
- 1, 1, 1, 0
実際にパターン数は合致している
最後に後ろのdp[i-1][j]はjのi未満の分割の総数だからそれを足して
dp[i][j] = dp[i][j-i] + dp[i-1][j]
となる