【Goで学ぶコンピューターサイエンス】動的計画法(DP)

動的計画法の基本概念

分割と再利用

動的計画法では、問題を部分問題に分割し、部分問題の解を保存して再利用します。この再利用により、同じ計算を繰り返すことを防ぎ、効率的に解を求めます。

Goサンプルコード(フィボナッチ)

package main

import "fmt"

func fibonacci(n int) int {
	if n <= 1 {
		return n
	}
	return fibonacci(n-1) + fibonacci(n-2)
}

// 再帰しながら計算結果をメモしておく
func fibonacciMemo(n int, memo map[int]int) int {
	if n <= 1 {
		return n
	}
	if _, exists := memo[n]; !exists {
		memo[n] = fibonacciMemo(n-1, memo) + fibonacciMemo(n-2, memo)
	}
	return memo[n]
}

// 再帰はせず、ループで計算結果をメモしておく
func fibonacciDP(n int) int {
	if n <= 1 {
		return n
	}
	dp := make([]int, n+1)
	dp[0], dp[1] = 0, 1
	for i := 2; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}
	return dp[n]
}

func main() {
	n := 10
	memo := make(map[int]int)
	fmt.Println("Fibonacci number:", fibonacci(n))
	fmt.Println("FibonacciMemo number:", fibonacciMemo(n, memo))
	fmt.Println("FibonacciDP number:", fibonacciDP(n))
}

フィボナッチで30まで数えるベンチマーク

goos: darwin
goarch: amd64
pkg: go-cs
cpu: Intel(R) Core(TM) i5-7500 CPU @ 3.40GHz
BenchmarkFibonacci-4                 282           4153664 ns/op               0 B/op          0 allocs/op
BenchmarkFibonacciMemo-4          324370              3128 ns/op            2216 B/op          6 allocs/op
BenchmarkFibonacciDP-4          12091509             97.58 ns/op             256 B/op          1 allocs/op
PASS
ok      go-cs   4.393s

参考として再帰のイメージ

呼び出された関数はコールスタックに積まれていき、積まれている一番上のものから処理していく(LIFO)

fibonacciMemo(10)
  fibonacciMemo(9)
    fibonacciMemo(8)
      fibonacciMemo(7)
        fibonacciMemo(6)
          fibonacciMemo(5)
            fibonacciMemo(4)
              fibonacciMemo(3)
                fibonacciMemo(2)
                  fibonacciMemo(1) -> 1
                  fibonacciMemo(0) -> 0
                fibonacciMemo(2) -> 1
              fibonacciMemo(3) -> 2
            fibonacciMemo(4) -> 3
          fibonacciMemo(5) -> 5
        fibonacciMemo(6) -> 8
      fibonacciMemo(7) -> 13
    fibonacciMemo(8) -> 21
  fibonacciMemo(9) -> 34
fibonacciMemo(10) -> 55

Goサンプルコード(ナップサック問題)

重さと価値が与えられたアイテムのリストから、重さの制限内で価値の最大化を目指す問題

package main

import "fmt"

func knapsack(weights, values []int, capacity int) int {
    n := len(weights)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, capacity+1)
    }

    for i := 1; i <= n; i++ {
        for w := 0; w <= capacity; w++ {
            if weights[i-1] <= w {
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]]+values[i-1])
            } else {
                dp[i][w] = dp[i-1][w]
            }
        }
    }
    return dp[n][capacity]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    weights := []int{2, 3, 4, 5}
    values := []int{3, 4, 5, 6}
    capacity := 5
    fmt.Println("Maximum value:", knapsack(weights, values, capacity))
}

Maximum value: 7

Goサンプルコード(最長共通部分列)

2つの文字列を比べて、同じ順番で出てくる文字をつなげていったら、どれが一番長くなるかを探すこと

package main

import "fmt"

func lcs(s1, s2 string) int {
    m, n := len(s1), len(s2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if s1[i-1] == s2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    return dp[m][n]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    s1 := "AGGTAB"
    s2 := "GXTXAYB"
    fmt.Println("Length of LCS:", lcs(s1, s2))
}

Length of LCS: 4