whileD'iary

日記とか

蟻本の分割数の問題を整理

目的

僕には何を言っているのかさっぱりだったので、他の方の解説を見ながら整理して理解する

分割数

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]

となる

参考サイト

Tech Tips: 分割数を考える

分割数の漸化式がよくわかんなかったから軽く整理した - 迷いませんか?