dpのin-place化について、そしてインラインdpへ【競技プログラミング】

はじめに

• dpの高速化手法の一つにin-place化という手法がある事を知ったので、頭に刻みつけることとした。
• in-place化って名前だけ聞くと、何か凄いような気がしちゃうけど、「使用する変数を減らして、メモリ使用量を減らそうよ」というだけの話です。なので、in-place化で使用メモリ量は減らせるけど、高速化に繋がるかどうかは不明です。
  • でも、例えば、in-place化で二次元のdp配列を一次元にして、forループを一つ減らす事ができれば、高速化になるよね！

in-place化の具体例（フィボナッチ数列）

• 言葉だけだと意図が伝わらないので、「dp初歩ならフィボナッチ」という格言に基づき、フィボナッチ数列での例を示します。ちなみに、コードは生成AIに作らせたよ。
• dpを使った場合

func fibonacci(_ n: Int) -> Int {
    if n <= 1 {
        return n
    }
    
    // 配列を用意して初期値を設定
    var dp = [Int](repeating: 0, count: n + 1)
    dp[0] = 0
    dp[1] = 1
    
    // 配列を使ってDPテーブルを埋めていく
    for i in 2...n {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    
    return dp[n]
}
let n = 10
print("Fibonacci(\(n)) = \(fibonacci(n))")

• 上記をin-place化した場合

func fibonacci(_ n: Int) -> Int {
    if n <= 1 {
        return n
    }
    
    var a = 0
    var b = 1
    
    for _ in 2...n {
        let temp = a + b
        a = b
        b = temp
    }
    
    return b
}

let n = 10
print("Fibonacci(\(n)) = \(fibonacci(n))")

• お分かりいただけただろうか？
• in-place化前のdpを使ったコードでは、変数はdp[0]〜dp[n]までのn+1個必要だったけど、in-place化によりa,bの2つだけで済むようになったね。
• これでin-place化が何を目的としているかイメージは出来たかな？

少し高度なケース（ナップサック問題）

• 「dp中級はナップサック」という格言に基づき、0-1ナップサック問題をin-place化してみます。
• 前提として、荷物の個数をN、ナップサックの容量をWとして、荷物の重さの配列をws、荷物の価値の配列をvsとします。
• まず先に、通常のdpを使って解きます。dp[i][w]は、下記状態における、解答（最大化された価値合計）です。
  • i:荷物(i in 0..<N)のうち、0..<iまでの荷物について、入れる/入れないを選択済み。
  • w:ナップサックの容量がw
• よって、求める解はdp[N][W]となります。
• 生成AIに作らせたコードに若干の修正を加えたのが下記コードです。

extension Array {
    init(_ cnt: Int, _ v: Element) {
        self = [Element](repeating: v, count: cnt)
    }
    init<T>(_ cnt2:Int, _ cnt1:Int, _ v:T) where Element == [T] {
        self = [[T]](cnt2,[T](cnt1,v))
    }
}

func knapsack(_ N:Int,_ W:Int,_ ws:[Int],_ vs:[Int]) -> Int {
    var dp = [[Int]](N+1,W+1,0)

    for i in 0..<N {
        for w in 0...W {
            if w >= ws[i] { // 荷物[i]を入れることが出来る場合
                dp[i + 1][w] = max(dp[i][w], dp[i][w - ws[i]] + vs[i])
            } else { // 荷物[i]を入れることが出来ない場合
                dp[i + 1][w] = dp[i][w]
            }
        }
    }
    // print(dp)
    return dp[N][W]
}

• 上記を実行した場合の例は以下のとおりです。

// 実行例
let N = 4
let W = 5
let weights = [2, 1, 3, 2]
let values = [3, 2, 4, 2]
print(knapsack(N,W,weights,values)) // 結果: 7

/// 上記例を解いたときのdpは以下のとおりです。分かり易いように改行を入れています。
[ [0, 0, 0, 0, 0, 0]  // i = 0 - 荷物を一つも入れてないので、全て0
, [0, 0, 3, 3, 3, 3]  // i = 1 - (重さ2、価値3)の荷物について判定。容量2以上で荷物が入ります。
, [0, 2, 3, 5, 5, 5]  // i = 2 - (2,3)(1,2)の荷物について判定。重さ合計1(価値2),2(価値3),4(価値5)の組み合わせがあります。
, [0, 2, 3, 5, 6, 7]  // i = 3 - (2,3)(1,2)(3,4)の荷物について判定。以下略
, [0, 2, 3, 5, 6, 7]] // i = 4

• ナップサック問題自体の解説は省きます。
  • ちなみに、リンク先の過去投稿と今回では、dpの設定が異なるから気を付けて。
  • in-place化では、解答がdp[0][...]になる過去投稿の方式では都合が悪くて、dp[N][...]が解答になる方が良いのです。
• 続いて、in-place方式でのコードを書きます。

func knapsackInPlace(_ N:Int,_ W:Int,_ ws:[Int],_ vs:[Int]) -> Int {
    var dp = [Int](W+1,0)

    for i in 0..<N {
        for w in (ws[i]...W).reversed() { // お尻(W)から実行するforループ
            dp[w] = max(dp[w], dp[w - ws[i]] + vs[i])
        }
        // print(i,dp)
    }
    return dp[W]
}

• dp配列が「通常のdp方式」では2次元だったのに、今回は1次元になりました。
  • まぁ、forループは相変わらず2重なので、高速化はしてないと思うけどね。
• なお、「通常のdp方式」と同じサンプルを実行したときのi in 0..<4でのdpは以下のとおりです。

0 [0, 0, 3, 3, 3, 3]
1 [0, 2, 3, 5, 5, 5]
2 [0, 2, 3, 5, 6, 7]
3 [0, 2, 3, 5, 6, 7]

• さて、解説をします。
• 基本的に、in-place化した場合のコードを最初から思いつく人はいないと思います。
• 普通の人は、「通常のdp方式」の形を見て、in-place化が出来ないかなぁと考えるわけです。
• 普通の人らしく、改めて、元のdpを見てみましょう。いったん、どのような内容の問題だったかを忘れてしまって良いです。dpの遷移だけを考えましょう。
• in-place化された「通常のdp方式」の箇所はここです。

        for w in 0...W {
            if w >= ws[i] { // 荷物[i]を入れることが出来る場合
                dp[i + 1][w] = max(dp[i][w], dp[i][w - ws[i]] + vs[i]) // -- ㋐
            } else { // 荷物[i]を入れることが出来ない場合
                dp[i + 1][w] = dp[i][w] // -- ㋑
            }
        }

• in-place化された後のループは次のように変換されました。

        for w in (ws[i]...W).reversed() { // お尻(W)から実行するforループ
            dp[w] = max(dp[w], dp[w - ws[i]] + vs[i])
        }

• 上記のとおり、二次元dp[i][w]が1次元減ってdp[w]になりました。とはいえ、外側のfor-iループは残っているので、変数dp[w]を各iで使い回すと言うことになります。フィボナッチの例での変数a,bに相当するものが、dp[w]ということです。
• まず、フィボナッチの例で、in-place化が出来た理由を考えます。
  • dp[i]の計算においては、dp[i-2]、dp[i-1]しか使用しておらず、dp[i-3]やdp[i-4]は使ってないです。
  • よって、dp[i-2],dp[i-1]を変数a,bに変えて、この変数のみを使ってループを回したと言うことです。
• 次にナップサック問題を考えます。
  • dp[i+1][...]の計算において、dp[i][...]しか使用してないので、dp[i-1][...]は不要となります。
  • おぉ、in-place化出来るじゃん！具体的に言えば、[i]の次元を削って、dp[...]のみのdpとします。
  • 強引にやる場合の手法
    • dp[...]と同型のtemp[...]という配列を用意しておきます。
    • 遷移iの状態での計算が終わった後、dp[...]の内容をtemp[...]にコピーします。
    • 遷移i+1の状態で、temp[...]を使って、dp[...]を計算します。そして、また、dpをtempにコピーします。 （...以下、ループ）
  • おや、ナップサック問題でもin-place化が出来るのは分かったけど、実際の出来上がりのコードを見ると、temp配列なんてないよね？dp[w]だけで済ませてます。
  • これは、一休さんのトンチのように、頭をひねって見つけた綺麗な手順があるからです。
  • 綺麗な手順の考え方
    • ㋐を見ると、dp[i+1][w]の計算で、dp[i][w]とdp[i][w-ws[i]]が使われてます。
      • このdp[w-ws[i]]がくせ者です。当たり前の話ですが、「w-ws[i]」は「w」より値が小さいです。よって、in-place化後のfor-w文でdp[w]を計算する際、wを頭から塗り替えてしまうと、遷移i＋1でのdp[w]の計算をする前にdp[w-ws[i]]が先に塗り替えられてしまい、遷移iでの情報が失われてしまいます。
      • だ、け、ど、for-w文をWから降順に回してあげれば大丈夫！dp[w-ws[i]]の方が後に塗り替えられるので、遷移iでのdpの情報が使える！解決！
    • ㋑については、何もする必要ないのが分かるよね？だって、in-place後のdp[w]について言えば、dp[w]=dp[w]をしているのと同じ。だから不要なんです。
  • これで、in-place化後のループの意味は分かったかな？
  • ダメ押しで、in-place化前のdp[i][w]とin-place化後のdp[w]を並べてみるよ。同じでしょ？
    
    

その他のケース(LIS)

• 以前紹介したLISは、実はin-place化された後でdpが2次元から1次元に落とされていたんだよね。
• じゃあ、元の2次元だったときのdpはどうだったかを見てみよう。
• dp[i][j]：元の配列がnums[0..<N]であり、このうちnums[0..<i]から単調増加の部分列を作り、最後の要素をnums[j]とする縛りを与える場合の部分列の最長の長さ。
  • この設定のdpについては注意が必要。
  • dpの二次元配列の初期化時に値を全部0にすると、dp[0][0]=0だったり、dp[2][0]=0だったりする。でも、これは異常な値だよ。
  • だって、長さ0なのに、部分列のお尻のインデックスが「0」とかあり得ない。
  • お尻のインデックスが存在すると言うことは、dp[i][j]≧1の場合に限る。だから、dp[i][j]=0のときは、初期化直後の「特殊な状態」と言うことを覚えておいてね。
    • まぁ、そもそも、そんな紛らわしいdpを設定すんなよ！と思うかもしれないけど、初期値を-1として未計算と分かり易くすると、それはそれでコードが複雑になるんだよ。スマヌ。

func lengthOfLIS(_ nums: [Int]) -> Int {
    
    let n = nums.count
    var dp = [[Int]](n+1,n,0) // 省略記法
    
    for i in 0..<n {
        for j in 0...i {
        
            // ㋐新登場のnums[i]をお尻とする場合（長さが1増える）
            if dp[i][j] == 0 // 「特殊な状態」が登場！既存のお尻がないので、nums[i]を「頭に追加」
                || nums[i]>nums[j] { // 既存のお尻より値が大きければ、「お尻交代」
                // dp[i+1][i] = dp[i][j] + 1 -- 「お尻交代」だけならコレで良い                
                dp[i+1][i] = max(dp[i+1][i],dp[i][j]+1) // 「頭に追加」で1に引き下げられるのを防ぐため、max関数で防御！
            }
            
            // ㋑nums[i]をスルーする場合
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])     

        }
    print(i,dp[i])
    }
    print(n,dp[n])

    return dp[n].max()!
}

• 実行例は以下のとおり

// 実行例
let A = [7, 9, 2, 5, 3, 7, 10, 4]
print("最長増加部分列の長さは \(lengthOfLIS(A)) です。") // 最長増加部分列の長さは 4 です。

/// 実行後のi毎のdp[i]の中身は下記のとおり
0 [0, 0, 0, 0, 0, 0, 0, 0]
1 [1, 0, 0, 0, 0, 0, 0, 0]
2 [1, 2, 0, 0, 0, 0, 0, 0]
3 [1, 2, 1, 0, 0, 0, 0, 0]
4 [1, 2, 1, 2, 0, 0, 0, 0]
5 [1, 2, 1, 2, 2, 0, 0, 0]
6 [1, 2, 1, 2, 2, 3, 0, 0]
7 [1, 2, 1, 2, 2, 3, 4, 0]
8 [1, 2, 1, 2, 2, 3, 4, 3]
// ちなみに、㋐のループでmax関数でdp[i+1][i]を防御しないと、上記の0以外の数値は全て1になってしまいます。
// 例えば、上記でdp[2][1]=2になっています。
//    これは、i=1におけるfor jループ(j in 0...1)で計算されたものです。
//    j=0のとき、「お尻交代」により、dp[2][1] = dp[1][0](=1) + 1 で、2となります。
//    もし、max関数で防御しないと、
//    j=1のとき、「頭に追加」により、dp[2][1] = dp[1][1](=0) + 1 で、1で上書きされてしまいます。

• 上記dp[i+1][...]は、dp[i][...]のみから計算されるため。dp[i-1]以前の古いdp配列は不要なので、前述の強引な手法（仮置き用の配列tempを使う手法）を使えば、現時点でもin-place化は可能です。
• とはいえ、基本的にそのような強引手法を使ってもメモリ使用量は減らせても、高速化できるわけでもないから、あまり旨みはないよね。と言うことで、強引じゃないスマートなin-place化のために、まずは、二次元配列時点のdpを見直します。
  • さっきのdp[i][j]：元の配列がnums[0..<N]であり、このうちnums[0..<i]から単調増加の部分列を作り、最後の要素をnums[j]とする縛りを与える場合の部分列の最長の長さ。
  • 新しいdp[i][k]：iの意味は同じ。kを最長部分列の長さとし、dpはLISの長さ=kを実現する「最小のお尻」の値。
    • 例えば、nums = [7, 9, 2, 5, 3, 7, 10, 4]のとき、i=5,k=2となる部分列は以下の3つ。
    • [7 9],[2 5],[2 3]
    • 最も小さいお尻が3なので、dp[5][2]=3となる。
      • だけど、初期値はどうしよう。小さい値に更新していくから、デカい値として、inf(= Int.max / 2)でいいかな。
      • あと、dp[i][0]をどうしよう、最長文字列の長さ0を実現するお尻なんて存在しないから、便宜的に無理やり「-1」でも入れておくかな。下で出てくるけんちょんさんの図は「0」を入れているけど、元の配列numsの要素ではないことが分かりづらいんだよね。-1にしておけば、「おっ、何か違う！」って分かるでしょ。
  • この新しいdpを使ったときのLISの解答は、dp[N].indices.filter{dp[N][$0] < inf}.last!になるね。swiftを使ってない人には分かりづらい呪文だけどゴメンね。swiftを始めたばかりの頃、上記みたいな配列操作が当たり前に出てきて、ムキー！と切れかけてたよ。
• 新しいdp[i][k]の更新方法は、けんちょんさんの解説に書いてあるけど、まぁ、けんちょんさん謹製の下図を見ればわかるかな？
  
• 新しいdpを使ってコードを書くと以下のとおり。

func lengthOfLIS(_ nums: [Int]) -> Int {
    
    let n = nums.count
    let inf = 99 // print時の見易さ重視。本来は、Int.max / 2にすべき。
    var dp = [[Int]](n+1,n+1,inf) // 省略記法 -- LISは最長nなので、kの範囲も0〜nとしておく
    
    for i in 0..<n {
        let ni = nums[i]
        var flg = true // dp[i+1][k]を塗り替えるタイミングは1回だけなので、「まだ」のフラグを立てる
        for k in 0...i+1 {
        
            if k == 0 {dp[i][0] = -1} // 枚数0を実現する番号は存在しないので、-1を入れておく
            
            dp[i+1][k] = dp[i][k]
        
            if flg && dp[i][k] > ni {
                dp[i+1][k] = ni
                flg = false // 実行札を裏返す
            }

        }
    // print(i,dp[i])
    }
    // print(n,dp[n])

    return dp[n].indices.filter{dp[n][$0] < inf}.last!
}

• で実行例は、

// 実行例
let A = [7, 9, 2, 5, 3, 7, 10, 4]
print("最長増加部分列の長さは \(lengthOfLIS(A)) です。") // 最長増加部分列の長さは 4 です。

///上記実行後のdp[i][k]の中身 -- inf = 99としたよ。Int.max / 2だと見づらいからね。
0 [-1, 99, 99, 99, 99, 99, 99, 99, 99]
1 [-1, 7, 99, 99, 99, 99, 99, 99, 99]
2 [-1, 7, 9, 99, 99, 99, 99, 99, 99]
3 [-1, 2, 9, 99, 99, 99, 99, 99, 99]
4 [-1, 2, 5, 99, 99, 99, 99, 99, 99]
5 [-1, 2, 3, 99, 99, 99, 99, 99, 99]
6 [-1, 2, 3, 7, 99, 99, 99, 99, 99]
7 [-1, 2, 3, 7, 10, 99, 99, 99, 99]
8 [-1, 2, 3, 4, 10, 99, 99, 99, 99]

• これのin-place化をどうやるかは言うまでもないよね。そもそも、dp[i][k]からdp[i+1][k]に帰るときに変更するところは、たった一つのkだけだから、もう最初から1次元dpで書きたかったくらいだよ。
• in-place化した後はこれ

func lengthOfLIS(_ nums: [Int]) -> Int {
    
    let n = nums.count
    let inf = 99 // 見やすさ重視
    var dp = [Int](n+1,inf) // 省略記法 -- LISは最長nなので、kの範囲も0〜nとしておく
    dp[0] = -1 // 枚数0を実現する番号は存在しないので、-1を入れておく
    
    for i in 0..<n {
        let ni = nums[i]
        for k in 0...i+1 { // このループって、つまり、upper_boundしてるだけでは？
        
            if dp[k] > ni {
                dp[k] = ni
                break
            }

        }
    // print(i,dp)
    }
    // print(n,dp)

    return dp.indices.filter{dp[$0] < inf}.last!
}

• 違いがわからないくらい変化がないでしょ。でも、2次元が1次元に変わっているよ。メモリ節約だね！forループは2重のまま変わりないけど。
• でも、ここまでスッキリさせたら、for_kループって、upper_boundをニブタン(O(logN))ではなく、全探索(O(N))してるだけって分かるよね。はい、コレでfor_kループの削除する方針が定まったね！
• ここから先はin-place化の話から離れるから、詳しくはコチラで。

そして真打ち、インラインdpへ（まずは、in-place化まで）

• in-placeと言う用語はこのdpのためだけにある言葉ではなく、「その場限りの」という意味です。メモ化配列dpを用意せず、変数a,bに値を格納して、その値がループ毎に塗り変わるので、「dpのin-place化」というのも、まぁ、一般的な表現と言えますね。
• 対してインラインdpは、skyさんによって名付けられたアルゴリズムです。
• 詳細はリンク先のskyさんの解説を見て貰えればと思いますが、簡単に説明すると、「in-place化」と「セグメント木」を使った高速化テクニックになります。
• skyさんの解説に則り、ARC073のd問題を解きましょう。
• 問題の内容
  • 2個の駒とN個のマス[0..<N]があり、駒は初期状態で、[A]と[B]に格納されている。
  • Q個のクエリが与えられ、処理時間を最小化した場合の秒数が解答となります。
  • 各クエリ(i in 0..<Q)では座標Xiが与えられ、駒のどちらかを座標Xiまで移動させる必要がある。
    • 駒は1マスずつしか移動できず、1マスの移動に1秒かかる。
    • なお、1つのマスに同時に2個の駒があっても良い。
• 入力例

8 3 1 8 // 8マス、3クエリ、駒の初期位置は、0-idxだと(0,7)
3 5 1 // 各クエリの座標は、0-idxだと2,4,0。

• 上記の解答は7秒
  • マス 0 のコマをマス 2 に動かす ⇒ 2秒
  • マス 7 のコマをマス 4 に動かす ⇒ 3秒
  • マス 2 のコマをマス 0 に動かす ⇒ 2秒
• さて、公式解説ではdpが3次元の場合から始めて、徐々に次元を減らすような流れだけど、3次元は省略して2次元版から説明するね。0-idx版で説明することとして、クエリ配列(位置座標)をXとするよ。
  • dp[i][a] : i 個のクエリを処理しており、コマが(a,X[i-1])にあるときの、最小秒数。
• このdpを使って解くと､以下のとおり。

extension Array {･･･} // 配列生成の省略表記用
let (N,Q,a0,x0) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1],$0[2]-1,$0[3]-1)}[0]
let X = readLine()!.split(separator:" ").map{Int($0)! - 1}

let inf = Int.max / 2
var dp = [[Int]](Q+1,N,inf) // dp[i][a]=infは、aの位置に駒がないということ

for i in 0..<Q {
    // 初期処理
    if i == 0 {
        dp[1][a0] = abs(X[0] - x0) 
        dp[1][x0] = abs(X[0] - a0)
        continue
    }

    // 遷移
    for a in 0..<N {
        if dp[i][a] == inf {continue} // aの位置に駒がなければスルー。この行がなくても、min関数により答えに差はない。

        // 駒xが動く場合　(立場変わらず)
        dp[i+1][a]      = min(dp[i+1][a]      , dp[i][a] + abs(X[i] - X[i-1]) ) 
        
        // 駒aが動く場合　(立場交代：駒a ⇔ 駒x)
        dp[i+1][X[i-1]] = min(dp[i+1][X[i-1]] , dp[i][a] + abs(X[i] - a)      )   

    }
}

print(dp[Q].min()!)

• うむ、ここまでは説明不要だよね。何のヒネりもないdpのコードです。
• 上記入力例実行時のi毎のdp[i][a]の中身は以下のとおり。なお、見やすさのため、inf=99としているよ。
  • クエリ3回実行後のdp[3]で最も値の小さい7秒が正解だね。
  • i=1を説明すると、駒が初期配置(0,7)にいて、マス2に駒を進める場合、駒0じゃない方を動かすときは5秒、駒7じゃない方を動かす場合は2秒、ってこと。
  • i=2を説明すると、駒は(0,2,7)の何処かに2つ有って、駒0じゃない方を動かすときは計7秒、駒2じゃない方を動かすときは計5秒、駒7じゃない方を動かすときは計4秒、ってこと。
  • i=3は省略！

0 [99, 99, 99, 99, 99, 99, 99, 99]
1 [5, 99, 99, 99, 99, 99, 99, 2]
2 [7, 99, 5, 99, 99, 99, 99, 4]
3 [11, 99, 9, 99, 7, 99, 99, 8]

• 提出したら、TLEだけじゃなく、REも出たよ。$N,Q≦2×10^5$だから、上記の二重forループでO(N･Q)で$10^8$を大きく超えちゃうからTLEは覚悟してたけど、やっぱり2次元配列で縦横それぞれ$10^5$だとREなのかな？
• で、ヒネらず作ったコードを見直すと、配るdpで作っているね。まぁ、直感的に作れるしね。でも、高度なアルゴリズムを導入しようとするときは、貰うdpで作った方が良いことが多い気がする。「貰うdpを累積和で高速化」とか、「貰うdpの高速化」とかね。
• で、実は今回も貰うdpに変えてから高速化します。まぁ、最初から貰うdpで書いておけよ、という話だけど。
• 貰うdp版は下記の通り。for-aループのみ差し替えます。

    for a in 0..<N {
        if a != X[i-1] {
            // ①駒xが動く場合　(立場変わらず)
                if dp[i][a] == inf {continue} // aの位置に駒がなければスルー。
                dp[i+1][a] =      dp[i][a] + abs(X[i] - X[i-1] )
        } else {
            // ②駒aが動く場合　(立場交代：新a=X[i-1] )
            for o in 0..<N { // oldなaの意味でo
                if dp[i][o] == inf {continue} // oの位置に駒がなければスルー。
                dp[i+1][a] = min( dp[i][o] + abs(X[i] - o      ) , dp[i+1][a] )   
            }
        }
    }

• 貰うdpにするため、for-oループが追加されちゃいました。このままだと、計算量が$O(Q･N^2)$で悪化ですね。...だが、それでいい！
• これからスッキリと綺麗にしていくよ！
  • まず、①②に書かれているif dp[i][a/o] == inf {continue}を省くことから始めます。
    • だって、infがInt.max/2のように大きければ、min関数で弾かれるから､なくても問題ないのよね。つまり、こまけえこたぁいいんだよ！の精神です。
  • そう考えると、①では、dp[i][a]⇒dp[i+1][a]は、|X[i]-X[i-1]|の平衡移動しているだけなので、for-aループを回す必要がなくなります。
  • すると、②の処理における、a=X[i-1]となるdp[i+1][a]の処理だけ特別扱いすれば良いと言うこと。1カ所だけ特別扱いってことは、in-place化が出来ちゃうって事だね！
• それでは、skyさんの説明で使われているdp表を使って説明します。
  
  
• 上記図の赤い部分が、処理②のdp[i][a]で、紫の部分がdp[i+1][a]に当たるよ。だから、a=X[i-1]ってこと。
• 図では、2次元配列を1次元配列で代用出来ると説明されているね！in-place化については、理解が進んでいるから、もう問題ないね。
• で、ここから､真打ち 「インラインdp」 の話が始まるよ。その前に、in-place化した新しいdpをdp[a]としておこうか。
• とりあえずin-place化すると、こんな感じになります。変更したdp配列設定以降だけ書くね。

var dp = [Int](N,inf) // dp[a]=infは、aの位置に駒がないということ

for i in 0..<Q {
    if i == 0 {
        dp[a0] = abs(X[0] - x0) 
        dp[x0] = abs(X[0] - a0)
        // print(i,dp)
        continue
    }
    
    let ax = X[i-1]
    let dx = abs(X[i]-X[i-1])
    
    var dpax = inf
    for o in 0..<N { // 計算量O(N) -- ②駒aが動く場合
        dpax = min( dp[o] + abs(X[i] - o) , dpax )   
    }
    dp[ax] = dpax

    dp = dp.map{$0 + dx} // 計算量O(N) -- ①駒xが動く場合
    dp[ax] = dp[ax] - dx
    
    // print(i,dp)
}
// print(Q,dp)

print(dp.min()!)

• 上記コードでは、①と②の処理の順番を入れ替えたよ。dpの「i-1」時点の情報が失われる前に、dp[X[i-1]]に渡さないといけないからね。
• さて、in-place化したから、後は高速化だね。もちろんセグ木を使うんだろうね。
• ①の処理では、for分を使ってないけど、map関数を使っているから、結局、計算量O(N)は使っちゃうんだよね。
  • でも①については、for-iループで都度map関数を行う必要はなくて、dxを累計するsumx変数をつくって、for-iループが終わった後に、dp.map{$0 + sumx}すれば良いから、①はクリア！
• ②の処理では、min関数を使っているから、セグ木が簡単にイケそうな気もするけど、|X[i]-o|を足した後のdpのmin値だからなぁ...どぎゃんしたらよかと？
• なお、実行結果は駒があり得ない位置でもinf(99)じゃなくなっちゃったよ。if dp[i][a/o] == inf {continue}を省いたからだね。

//i毎のdp[a]
0 [5, 99, 99, 99, 99, 99, 99, 2]
1 [7, 101, 5, 101, 101, 101, 101, 4]
2 [11, 105, 9, 105, 7, 105, 105, 8]
3 [11, 105, 9, 105, 7, 105, 105, 8]

//答え -- dpのmin値
7

インラインDPのキモ（in-place化後のセグ木適用）

• 前記の下記②処理を高速化したい。

    for o in 0..<N { // 計算量O(N) -- ②駒aが動く場合
        dpax = min( dp[o] + abs(X[i] - o) , dpax )   
    }

• 答えから言ってしまえば、セグ木を使うんだけど、ちょっと強引な手口を使う必要がある。ここで、説明すると話が長くなるから、詳しくは、リンク先を見てね。
• で、強引な手口とはどういう事かというと、dpの代わりに、dpl,dprという別の配列を用意して、こいつらをセグ木に食わせると言うこと。
  • dpl[k]：dp[k] + N - k
  • dpr[k]：dp[k] + k
• この新しい配列を使うと、dp[k] + abs(X[i] - k)は以下のように表せます
  • k < X[i] のとき、dpl[k] + X[i] - N
  • X[i] ≦ k のとき、dpr[k] - X[i]
• 具体的には、コードを見てね

class SegTree {･･･} // セグ木

extension Array {･･･} // 配列生成の省略記法の為のエクステンション

let (N,Q,a0,x0) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1],$0[2]-1,$0[3]-1)}[0]
let X = readLine()!.split(separator:" ").map{Int($0)! - 1}

let inf = Int.max / 2
// let inf = 99 // 本チャンでは使わないよ。
var dp = [Int](N,inf) // dp[a]=infは、aの位置に駒がないということ

// セグ木準備
var dpl = dp
var dpr = dp
for k in 0..<N {
    dpl[k] = dp[k] + N - k // k < X[i] のとき
    dpr[k] = dp[k] + k     // X[i] ≦ k のとき
}
var stl = SegTree(dpl)
var str = SegTree(dpr)
//セグ木update関数
func stupdt(_ k:Int){
    dpl[k] = dp[k] + N - k
    dpr[k] = dp[k] + k
    stl.update(k,dpl[k])
    str.update(k,dpr[k])
}

var sum_dx = 0

for i in 0..<Q {
    if i == 0 {
        dp[a0] = abs(X[0] - x0) 
        stupdt(a0) // セグ木アップデート！
        dp[x0] = abs(X[0] - a0)
        stupdt(x0) // セグ木アップデート！
        // print(i,dp,0) // dpの経過観察用
        continue
    }
    
    let ax = X[i-1]
    let dx = abs(X[i]-X[i-1])

    // var dpax = inf
    // for o in 0..<N { // oldなaの意味でo
    //     dpax = min( dp[o] + abs(X[i] - o      ) , dpax )
    let dpax = min(stl.query(0,X[i]) + X[i] - N , str.query(X[i],N) - X[i]) // セグ木で代替
    // }
    
    // dp[ax] = dpax
    // dp = dp.map{$0 + dx} // 計算量O() ⇒　for-iループから外にお引っ越し
    // dp[ax] = dp[ax] - dx
    
    dp[ax] = dpax - dx
    stupdt(ax) // セグ木アップデート！
    sum_dx += dx
    
    // print(i,dp,sum_dx) // dpの経過観察用
}
// print(Q,dp,sum_dx) // dpの経過観察用

dp = dp.map{$0 + sum_dx} // 計算量O() ← for-iループの中からお引っ越し

print(dp.min()!)

• 上記の実行結果は、こんな感じ。dp[a]の値は、セグ木導入前と比べてsum_dxだけズレていることが分かるね。

//i毎のdp[a]とsum_dx
0 [5, 99, 99, 99, 99, 99, 99, 2] 0
1 [5, 99, 3, 99, 99, 99, 99, 2] 2
2 [5, 99, 3, 99, 1, 99, 99, 2] 6
3 [5, 99, 3, 99, 1, 99, 99, 2] 6

//答え -- dpのmin値
7

• なお、提出したら200ms程度でACでした。
• ここまで、長い道のりだった...

おわりに

• 実は、「インラインdpって何？」と言う疑問から始まった投稿だったんだけど、結構大変だったよ。
• skyさんは、「1次元配列の一部だけを更新していくことによって、実際には2次元であるDPを上から下まで計算できる」ようにするのが、インラインdpと説明されているので、僕の下記理解で合ってるはず！
  • in-place化により、2次元dp⇒1次元dp
  • 元々2重forループだったモノを、dpの1次元化に合わせて、セグ木を使って内側のforループを破壊して高速化（for-iループ内側の計算量：O(N)⇒O(logN)）。
• まだ、インラインdpが体に染みついたとまで言えないから、そのうち、面白いインラインdp問題を見つけたら、続編を書きたいね。