動的計画法について勉強する - どこにでもいるSEの備忘録

まだまだAtCoderの勉強をこっそり続けてます。

www.nogawanogawa.work

今回は、AtCoderでも非常によく登場する動的計画法（DP）について勉強していきたいと思います。

DP（動的計画法） is 何？
- 例題を解いてみる
実際の問題を解いてみる
- ナップザック問題
- 最長共通部分列問題
参考文献
感想

DP（動的計画法） is 何？

wikipediaによると、動的計画法の定義はこんな感じの説明がされています。

細かくアルゴリズムが定義されているわけではなく、下記2条件を満たすアルゴリズムの総称である。
1. 帰納的な関係の利用：より小さな問題例の解や計算結果を帰納的な関係を利用してより大きな問題例を解くのに使用する。
2.計算結果の記録：小さな問題例、計算結果から記録し、同じ計算を何度も行うことを避ける。帰納的な関係での参照を効率よく行うために、計算結果は整数、文字やその組みなどを見出しにして管理される。動的計画法 - Wikipedia

かっちりとした定義があるわけではなく、

漸化式
メモ化

といったものを適用できるアルゴリズム、というくらいのぼんやりした感じになっているようですね。

例題を解いてみる

理屈から入るより、実践したほうが多分伝わると思いますので、一つ例題をやってみます。

atcoder.jp

この問題は、どの足場を通って目的地に行くかというパターン数が非常に大きくなります。このパターンを全通り確認して解を求めていては計算が間に合いません。

そこで、「各足場へたどり着くまでの最小コスト」を記録しながら端からコストを記録していきます。そうすることで、すべてのパターンを計算することなく、足場の数Nの数の計算で解を求めることができます。

こういった、途中経過を記録したがら探索を進める技法をメモ化と呼ぶようです。

クリックして展開

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "math"
)

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
    sc.Scan()
    i, e := strconv.ParseInt(sc.Text(),10,32)
    if e != nil {
        panic(e)
    }
    return int(i)
}

func main() {
    sc.Split(bufio.ScanWords)

    var N int
    fmt.Scanf("%d", &N)

    h := make([]int, N)
    for i:=0; i<N; i++{
        h[i] = nextInt()
    }

    dp := make([]int, N)

    dp[0] = 0
    dp[1] = int(math.Abs(float64(h[0] - h[1])))

    for i:=2; i<N; i++{
        dp_1 := int(math.Abs(float64(h[i] - h[i-1]))) + dp[i-1]
        dp_2 := int(math.Abs(float64(h[i] - h[i-2]))) + dp[i-2]

        if dp_1 < dp_2 {
            dp[i] = dp_1
        } else {
            dp[i] = dp_2
        }
    }

    fmt.Printf("%d\n", dp[N-1])
}

実際の問題を解いてみる

こちらに典型的な動的計画法の問題が詰まった素晴らしいコンテストがあるので、こちらから拝借して解いてみたいと思います。

atcoder.jp

ナップザック問題

atcoder.jp

ごく一般的なナップザック問題を解いてみたいと思います。今回は2次元配列を用いて考えてみたいと思います。

縦軸を容量の上限、横軸に品物の番号をとった行列を考えます。このとき、縦軸の値を超えないように、対象の列のより左側の品物を自由に使ったときの価値の最大値とその時の使用容量を各マスに記録していくことにします。これを、この二次元配列のすべてのマスに対して計算して、最後に右下のマスの値はすべての品物について、ナップザックの容量を超えないように品物を入れたときの最大価値と同義になります。

クリックして展開

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int64 {
    sc.Scan()
    i, e := strconv.ParseInt(sc.Text(),10,64)
    if e != nil {
        panic(e)
    }
    return i
}

func main() {
    sc.Split(bufio.ScanWords)

    var N, W int64
    fmt.Scanf("%d %d", &N, &W)

    w := make([]int64, N)
    v := make([]int64, N)

    var i,j int64
    for i=0; i<N; i++{
        w[i] = nextInt()
        v[i] = nextInt()
    }

    dp := make([][][]int64, N)
    for i=0; i<N; i++{
        dp[i] = make([][]int64, W+1)
        for j=0; j<=W; j++{
            dp[i][j] = make([]int64, 2)
        }
    }

    for j=0; j<=W; j++{
        if w[0] <= j{
            dp[0][j][0] = w[0]
            dp[0][j][1] = v[0]
        }
    }

    for i=1; i<N; i++{
        for j=0; j<=W; j++{
            if j - w[i] >= 0{
                if dp[i-1][j-w[i]][1] + v[i] >= dp[i-1][j][1]{
                    dp[i][j][0] = dp[i-1][j-w[i]][0] + w[i]
                    dp[i][j][1] = dp[i-1][j-w[i]][1] + v[i]
                } else {
                    dp[i][j][0] = dp[i-1][j][0]
                    dp[i][j][1] = dp[i-1][j][1]
                }
            } else {
                dp[i][j][0] = dp[i-1][j][0]
                dp[i][j][1] = dp[i-1][j][1]
            }
        }        
    }

    fmt.Printf("%d\n", dp[N-1][W][1])
}

最長共通部分列問題

atcoder.jp

あと有名な問題として、最長共通部分列問題というものがあります。今回の問題では、2つの文字列のそれぞれについて、共通する最大の長さの部分文字列を求める問題です。

この問題では、漸化式を使用して考えます。

長さS、Tの文字列から一文字ずつ除いた長さS-1、T-1の文字列について、共通する最大文字列がわかっているとき、長さS、Tの文字列の共通する部分文字列は、

加わった文字について、S[i] = T[j]のとき
- 長さS、Tの文字列から一文字ずつ除いた長さS-1、T-1の文字列について、共通する最大文字列 + 追加された文字
それ以外
- 長さSの文字列から一文字ずつ除いた長さS-1、Tの文字列に関する共通する最大文字列
- 長さTの文字列から一文字ずつ除いた長さS、T-1の文字列に関して共通する最大文字列

のどれかになるはずです。これをS × Tの行列について端から求めれば、求める解にたどり着きます。

クリックして展開

package main

import (
    "fmt"
    "strings"
)

func main() {

    var s, t string
    fmt.Scanf("%s", &s)
    fmt.Scanf("%s", &t)

    S := strings.Split(s, "")
    T := strings.Split(t, "")

    dp := make([][]int, len(S)+1)
    for i:=0; i<len(S)+1; i++{
        dp[i] = make([]int, len(T)+1)
    }

    for i:=1; i<len(S)+1; i++{
        for j:=1; j<len(T)+1; j++{
            dp[i][j] = dp[i-1][j]
            if dp[i][j] < dp[i][j-1] {
                dp[i][j] = dp[i][j-1]
            }
            if s[i-1] == t[j-1] && dp[i][j] < dp[i-1][j-1]+1 {
                dp[i][j] = dp[i-1][j-1] + 1
            }
        }
    }

    var result string = ""
    i, j := len(S), len(T)
    for (i>0) && (j>0) {
        if (S[i-1] == T[j-1]) && (dp[i-1][j-1]+1 == dp[i][j]){
            result = S[i-1] + result
            i --
            j -- 
            continue
        }
        if dp[i][j-1] == dp[i][j] {
            j--
        } else {
            i--
        }
    }

    fmt.Printf("%s\n", result)
}