迷いませんか?

プログラミング、電子工作、ゲーム・・・etc、色々やるけど中途半端なブログです。

分割数の漸化式がよくわかんなかったから軽く整理した

蟻本つらい!!!!!

蟻本を頑張って進めてますが、DPで漸化式をうまく立てられず苦しんでます
ほんと辛い、なれってわかってるけど慣れる気がしない

そしてさらに分割数とかいう漸化式の解説すらよくわかんない問題が来たので一生懸命考えて軽く整理してみた
基本的には蟻本の解説をかみ砕いていく感じにしか無理です><
 

分割数

まず、蟻本とは逆になるがdp[n][m]をnのm分割とし,
とりあえずdp[0][0]は1とする

ここでは例として5の3分割を考える いくつに分割されているかで分類する

  • 1つ
    • 5 + 0 + 0
  • 2つ
    • 4 + 1 + 0
    • 3 + 2 + 0
  • 3つ
    • 3 + 1 + 1
    • 2 + 2 + 1

このとき、 3分割なので足りない分を0で埋める
そして0がないところに注目してそれぞれの項から1ずつ引くと

2 + 0 + 0
1 + 1 + 0

になる
3つの項から1ずつ引いたので合計は5から5-3=2になっている
そして3つに分割されている
よって元の分割で3つに分割された部分の数は、2の3分割の総数に等しい

残りの部分はそのまま5の2分割の総数に等しくなる
なので漸化式は

dp[i][j] = dp[i - 1][j] + dp[i - j][j]
dp[i][j] = dp[i][j-1] + dp[i-j][j]

urutomさんのご指摘により修正させていただきました。
ありがとうございます!

となる

自分で書いてても意味わかんなくなった