はじめに

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

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

設定

株価のリスト 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]みたいなリストで実際に更新してみると理解できるかも

頑張りましょう；；