【初心者がかく】動的計画法（株価の変動）【競技プログラミング】

はじめに

私は本当に動的計画法（を含む競技プログラミング）が苦手で...

とりあえず株価の変動だけでも頑張り，ちゃんと理解できた気がするので書き殴る！
おバカな人向けです！

設定

• 株価のリスト prices が与えられる（例：prices = [3, 2, 6, 5, 0, 3]）
• 株を買う（1回）→売る（1回）の操作を1回の取引とする
• 最大 k回の取引 をして得られる利益を最大化する方法を考える

コード

実際のコードは以下です．まだ理解しなくて良い．空間計算量が良いverはリンク先を参照してください．

def calcurate_max_profit(prices: list[int], k: int) -> int:
    n = len(prices)
    # DPテーブルの初期化
    dp = [[0] * n for _ in range(k + 1)]
    for j in range(k):
        maxDiff = -prices[0]
        for i in range(1, n):
            dp[i][j] = max(dp[i - 1][j], maxDiff + prices[i])
            maxDiff = max(maxDiff, dp[i][j - 1] - prices[i])

    return dp[-1][k]

考え方

• dp: i日目にj回目の"売り"が完了している場合の最大利益
  • 0日目なら全部0！
• maxDiff: i日目にj回目の"買い"が完了している場合の最大利益
  • 例えば，基本的にj=1（1回しか買えない場合）の時は負

むずいポイント

dp

初期値：

全て0で埋める

更新：

• i日目に株を売らない場合
  • dp[i][j] = dp[i-1][j]
  • ここは理解できる
• i日目に株を売る場合
  • dp[i][j] = maxDiff + prices[i]
    • これはむずい
    • つまり，"買い"に対してprices[i]で売るので加算する
    • 例えばmaxDiffが-2で，その時の株価が10なら，dp[i][j]=8

すなわち，dp[i][j] = max(dp[i-1][j], maxDiff + prices[i])

maxDiff

初期値：

maxDiff = -prices[0]

つまり，初日で買った場合を初期値とする

更新：

• これまでの株価のほうが安い場合
  • maxDiff = maxDiff
• 今日（i日目）の株価のほうが安い場合
  • maxDiff = dp[i][j-1] - prices[i]
    • 前回（j-1回目）の"売り"までで，今日までの最大利益から，今日の株価を引く
      • 買うからね

すなわち，maxDiff = max(maxDiff, dp[i][j-1] - prices[i])

まとめ

動的計画法はむずい！！

これでも理解できなかったら，[3, 0, 5, 7, 4]みたいなリストで実際に更新してみると理解できるかも

頑張りましょう；；