09 Dec 2015, 10:42

TopCoderで動的計画法とメモ化再帰の問題を解いてみる(Python)

以下の参考書を元に、TopCoderの対策をしています。

今日は、動的計画法とメモ化再帰について勉強しました.

動的計画法(Dynamic Programming)

[sourcecode language=”text” title=”” ]
対象となる問題を複数の部分問題に分割し、
部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ
[/sourcecode]

分類

<div class="outline-text-3" id="text-orgheadline2">
  <p>
    動的計画法には、トップダウン方式、ボトムアップ方式の二つがある. 以下のように呼ばれることが多い.
  </p>

  <ul class="org-ul">
    <li>
      再帰関数のメモ化 ・・・メモ化再帰、メモ化、トップダウン方式
    </li>
    <li>
      漸化式 + ループ ・・・動的計画法、分割統治法、ボトムアップ方式
    </li>
  </ul>
</div>

トップダウン方式(メモ化再帰)

<div class="outline-text-3" id="text-orgheadline3">
  <p>
    一度計算した結果を覚えておいて、 同じ計算をしようとしたときに記憶していた値を利用する.
  </p>

  <p>
    再帰関数を利用することで、問題を解く.
  </p>
</div>

ボトムアップ方式(漸化式)

<div class="outline-text-3" id="text-orgheadline4">
  <p>
    漸化式を立てて、順々に漸化式を解いていく.
  </p>

  <p>
    for文を回すことで、問題を解く.
  </p>
</div>

問題

SRM413 Div1 Medium

<div class="outline-text-3" id="text-orgheadline5">
  <p>
    以下の問題をPythonで解いてみる.
  </p>

  <ul class="org-ul">
    <li>
      <a href="http://www.itmedia.co.jp/enterprise/articles/1003/06/news002_3.html">最強最速アルゴリズマー養成講座:アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった (3/5) &#8211; ITmedia エンタープライズ</a>
    </li>
    <li>
      <a href="https://community.topcoder.com/stat?c=problem_statement&pm=9922&rd=13504">https://community.topcoder.com/stat?c=problem_statement&pm=9922&rd=13504</a>
    </li>
  </ul>
</div>

<div id="outline-container-orgheadline6" class="outline-4">
  <h4 id="orgheadline6">
    動的計画法
  </h4>

  <div class="outline-text-4" id="text-orgheadline6">
    <p>
      <b>まとめらる処理をまとめて、同じ計算を行わないようにする</b>
    </p>

    <p>
      途中経過をメモしておいて、次の計算で使うというのが動的計画法. ここでは、i を順に計算していく.
    </p>

    <p>
      [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> class InfiniteSequence2:<br /> def calc(self, n, p, q, x, y):<br /> dp = [0 for i in range(n + 1)]<br /> dp[0] = 1
    </p>

    <p>
      for i in range(1, n + 1):<br /> nexta = i / p &#8211; x<br /> nextb = i / q &#8211; y
    </p>

    <p>
      if nexta <= 0: a = 1 else: a = dp[nexta] if nextb <= 0: b = 1 else: b = dp[nextb] dp[i] = a + b return dp[n] [/sourcecode] </div> </div> 

      <div id="outline-container-orgheadline7" class="outline-4">
        <h4 id="orgheadline7">
          深さ優先探索
        </h4>

        <div class="outline-text-4" id="text-orgheadline7">
          <p>
            トップダウンで探索をしていく.
          </p>

          <p>
            [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> class InfiniteSequence2:<br /> def calc(self, n, p, q, x, y):<br /> return self.dfs(n, p, q, x, y)
          </p>

          <p>
            def dfs(self, n, p, q, x, y):<br /> if n <= 0: return 1 return self.dfs(n / p - x, p, q, x, y) + self.dfs(n / q - y, p, q, x, y) [/sourcecode] </div> </div> 

            <div id="outline-container-orgheadline8" class="outline-4">
              <h4 id="orgheadline8">
                メモ化再帰
              </h4>

              <div class="outline-text-4" id="text-orgheadline8">
                <p>
                  一度計算した点は覚えておいて、余計な計算をしないのがメモ化再帰.
                </p>

                <p>
                  [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> class InfiniteSequence2:<br /> def calc(self, n, p, q, x, y):<br /> self.memo = {}<br /> return self.dfs(n, p, q, x, y)
                </p>

                <p>
                  def dfs(self, n, p, q, x, y):<br /> if n <= 0: return 1 if n in self.memo: return self.memo[n] self.memo[n] = self.dfs(n / p - x, p, q, x, y) + self.dfs(n / q - y, p, q, x, y) return self.memo[n] [/sourcecode] </div> </div> </div> </div> 

                  <div id="outline-container-orgheadline10" class="outline-2">
                    <h2 id="orgheadline10">
                      Special Thanks
                    </h2>

                    <div class="outline-text-2" id="text-orgheadline10">
                      <ul class="org-ul">
                        <li>
                          <a href="http://www.itmedia.co.jp/enterprise/articles/1003/06/news002.html">最強最速アルゴリズマー養成講座:アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった (1/5) &#8211; ITmedia エンタープライズ</a>
                        </li>
                        <li>
                          <a href="http://www.itmedia.co.jp/enterprise/articles/1005/15/news002.html">最強最速アルゴリズマー養成講座:病みつきになる「動的計画法」、その淵に迫る (1/4) &#8211; ITmedia エンタープライズ</a>
                        </li>
                        <li>
                          <a href="http://shindannin.hatenadiary.com/entry/20131208/1386512864">動的計画法が苦手な人が、動的計画法が超苦手な人へアドバイスしてみる &#8211; じじいのプログラミング</a>
                        </li>
                        <li>
                          <a href="http://www.slideshare.net/iwiwi/ss-3578511">プログラミングコンテストでの動的計画法</a>
                        </li>
                      </ul>
                    </div>
                  </div>