動的計画法


プログラム


  1. 単純な方法

    def rangeSum(x, i, j):               # 配列 x の i 番目から j 番目までの和
      s = 0
      for k in range(i, j + 1):
        s = s + x[k]
      return s
    
    def maxSumRange(x):                  # 配列 x の部分要素和の最大値
      m = 0                              # 最大値の候補
      for i in range(0, len(x)):
        for j in range(i, len(x)):
          m = max(m, rangeSum(x, i, j))
      return m
    
  2. 漸化式を再帰プログラムに

    def ms(x, k):                        # 漸化式をそのまま再帰にしたもの
      if k == 0:
        return x[0]
      else:
        return max(x[k], ms(x, k - 1) + x[k])
    
    def maxSumRange(x):                  # 配列 x の部分要素和の最大値
      m = 0
      for i in range(0, len(x)):
        m = max(m, ms(x, i))
      return m
    
  3. 動的計画法を使ったプログラム

    def maxSumRange(x):
      m = 0
      ms = ita.array.make1d(len(x))     # 表を用意
      for i in range(0, len(x)):
        ms[i] = ms_core(ms, x, i)       # 表を埋める
        m = max(m, ms[i])
      return m
    
    def ms_core(ms, x, k):
      if k == 0:
        return x[0]
      else:
        return max(x[k], ms[k - 1] + x[k])def maxSumRange(x):
    
  4. lcs の再帰プログラム

    def commonDNA(x, y):
      return lcs(x, y, len(x), len(y))
    
    def lcs(x, y, i, j):
      if i == 0 or j == 0:
        return 0
      else:
        r = max(lcs(x, y, i - 1, j), lcs(x, y, i, j - 1))  # いずれにせよ考慮するケース
        if x[i - 1] == y[j - 1]:
          r = max(r, 1 + lcs(x, y, i - 1, j - 1))          # x[i - 1] == y[j - 1] なら考慮するケース
        return r
    
  5. lcs の動的計画法

    def commonDNA(x,y):
      n = len(x)
      m = len(y)
      lcs = ita.array.make2d(n+1,m+1)
      for i in range(0, n + 1):
        for j in range(0, m + 1):              # 「短い」場合から順に
          lcs[i][j] = fill(lcs, x, y, i, j)    # fill(lcs, x, y, i , j) = lcs(i, j)
      return lcs[n][m]
    
    def fill(lcs, x, y, i, j):
      if i == 0 or j == 0:
        return 0
      else:
        r = max(lcs[i - 1][j], lcs[i][j - 1])  # いずれにせよ考慮するケース
        if x[i-1] == y[j-1]:
          r = max(r, 1 + lcs[i - 1][j - 1])    # x[i - 1] == y[j - 1] なら考慮するケース
        return r
    

2022年1月16日作成
伊知地 宏
Copyright (C) Hiroshi Ichiji, 2022. All rights reserved.