2

下記、動的計画法を用いて分割数を求める問題についてです。
下記dp配列を定義し、漸化式を立て本問題を解くそうなのですが理解できていない点が三つあります。疑問点を上手く言語化できておりませんが解説いただけると幸いです。

わからない箇所

  1. 漸化式のdp[i][j-i]は予めi個を1個ずつi個の集合に割り当てて残ったj-i個をこの集合に割り当てるという考え方らしいのですがなぜそうするのか意図がわかりません。
  2. 直下例のように考えるそうなのですが、集合に一個ずつ割り当ててますがその下で6,0,0,0と0を割り当てていますがよろしいのでしょうか。
    例)10個を4個に分けるパターンは、まず集合が4ついるので、それぞれの集合に1個ずつ割り当て
    1, 1, 1, 1
    あとは、残った6個をこの4つの集合に割り振るパターン数を考えればよい。
    例えば、
    6, 0, 0, 0
    1, 1, 1, 3
    2, 2, 0, 2

  3. 動的計画法のイメージが全体的につかめておりません。

考え方

dp配列:dp[i][j]:=jのi分割の総和
漸化式:dp[i][j] = dp[i][j-i]+dp[i-1][j]

問題

n個のお互いに区別できない品物を、m個以下に分割する方法の総和を求めMで割ったあまりを答えなさい。

  • 入力

    n=4
    m=3
    M=10000

  • 出力

    4(1++2=1+3=2+2=4)

参照:プログラミングコンテンストチャレンジブック

1 件の回答 1

2

前提として

dp配列の意味を問題の表現に合わせて言うと
dp[i][j] => j 個のものを i 個以下に分割する方法の総和
です。漸化式中の不明な項 dp[i][j - i] 以外の項をこの表現に合わせると
dp[i][j]( j 個のものを i 個以下に分割する方法の総和) = dp[i][j - i] + dp[i - 1][j]( j 個のものを i - 1 個以下に分割する方法の総和)
となります。
つまり、 dp[i][j - i] は 「j 個のものを'ちょうど i 個'に分割する方法の総和」として漸化式の中に現れています。

以下では、

「'i 個以下'の分割」 を 「'要素が0個の集合を含んでもよい' i 個の集合への分割」
「'ちょうど i 個'の分割」 を「'要素が0個の集合を含まない' i 個の集合への分割」

と同視して話を進めます。

本題

以上を前提に

1.漸化式のdp[i][j-i]は予めi個を1個ずつi個の集合に割り当てて残ったj-i個をこの集合に割り当てるという考え方らしいのですがなぜそうするのか意図がわかりません。

'ちょうど i 個'の分割になるように、i 個の集合すべてに少なくとも1つずつ物が含まれてる状態にするためです。

2.直下例のように考えるそうなのですが、集合に一個ずつ割り当ててますがその下で6,0,0,0と0を割り当てていますがよろしいのでしょうか。

以下のように考えることで、 dp[i][j - i] が 「j 個のものを'ちょうど i 個'に分割する方法の総和」と同数であることが証明できます。

・まず、1個足される前の分割に要素が0個の集合があっても、1個足されることで要素が0個の集合はなくなるので、すべてに1個を足す操作後に「'要素が0個の集合を含まない' i 個の集合への分割」状態になっていることがわかります。

・一方で、要素が0個の集合を含まない i 個の集合への分割を考える場合。すべての集合から1個取り除くことができ、すべてから1個取り除くことで元の「'要素が0個の集合を含んでもよい' i 個の集合への分割」状態を復元できることがわかります(※これがチャレンジブックの「すべてのiでai>0ならば、{ai-1}はn-m個のm分割」という表現になります)。

つまり、要素が0個の集合を含むすべての集合に1個足す(もしくは取り除く)という操作を通じて、「j - i個の i 個以下の分割」と「j 個のちょうど i 個の分割」を一対一で対応させることができ、

dp[i][j - i] = j 個のものを'ちょうど i 個'に分割する方法の総和

を証明することができます。

3.動的計画法のイメージが全体的につかめておりません。

動的計画法の範疇にとどまりませんが、基本的な考え方は、解きやすい小問題に分解して解いて、その解を利用して元の問題を解くということです。動的計画法はこのような考え方のアルゴリズムのうち、小問題の解をメモ化しておくことで同じ問題を繰り返し解かなければいけない場合に高速に計算を行うことができるというものです。

動的計画法といった場合、チャレンジブックで行われているようなボトムアップ(小さい問題を計算してから大きい問題に取り掛かる)方式が使われることが多いですが、そこは本質的な部分ではありません。
特にイメージがつかみづらいのであれば、トップダウンな方法(関数の再帰呼び出しを使って必要に応じて小さい問題を解く方法など)を使って解くことを試みたほうがイメージはつかみやすいのではないかと思います。小さい問題であればメモ化せずそのまま解けますし、少々大きい問題でもメモ化再帰を使うことでボトムアップと同等の性能が期待できます。

ただ、これがわかったからと言って動的計画法を使いこなせるわけではありません。チャレンジブックでは簡単にやってのけてますが、どう分解するか、どうやって分解した結果から元の問題を解くかというのは互いに関係しあう(計算の仕方によって分解のしやすさが変わったり、分解の仕方で計算のしやすさが変わったりする)本質的に難しいことなのでいろいろ検討してみるほかありません。

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。