動的計画法（DP : Dynamic Programing）

動的計画法とは、対象となる問題を複数の部分問題に分割し、部分問題の計算結果を利用して、全体の問題を解く手法。

何はともあれ、サンプルを見てみよう。

サンプルコード

動的計画法 · ki-hi-ro/python@0872908

# 行と列を入力してください: 4 4
# 1 1 1 2
# 1 1 2 2
# 1 2 2 2
# 2 2 2 2

class Board:
    def __init__(self):
        self.H, self.W = map(int, input("行と列を入力してください: ").split())
        self.grid = self._read_board()

    def _read_board(self):
        """盤面の読み込み"""
        board = []
        for _ in range(self.H):
            board.append(list(map(int, input().split())))
        return board


class PathFinder:
    def __init__(self, board):
        self.board = board
        self.H = board.H
        self.W = board.W
        self.dp = [[0] * self.W for _ in range(self.H)]

    def compute_max_path_sum(self):
        """動的計画法で最大スコアを求める"""
        self.dp[0] = self.board.grid[0][:]

        for y in range(1, self.H):
            for x in range(self.W):
                candidates = []
                for dx in [-1, 0, 1]:
                    prev_x = x + dx
                    if 0 <= prev_x < self.W:
                        candidates.append(self.dp[y - 1][prev_x])
                self.dp[y][x] = self.board.grid[y][x] + max(candidates)

        return max(self.dp[-1])

    def display_dp_table(self):
        """DPテーブルを可視化"""
        print("\nDPテーブル:")
        for row in self.dp:
            print(*row)


def main():
    board = Board()
    path_finder = PathFinder(board)
    max_score = path_finder.compute_max_path_sum()
    print(f"\n最大スコア: {max_score}")
    path_finder.display_dp_table()


if __name__ == "__main__":
    main()

出力結果

行と列を入力してください: 4 4
1 1 1 2
1 1 2 2
1 2 2 2
2 2 2 2

最大スコア: 8

DPテーブル:
1 1 1 2
2 2 4 4
3 6 6 6
8 8 8 8

解説

全体の流れはmain関数で定義している。

def main():
    board = Board()
    path_finder = PathFinder(board)
    max_score = path_finder.compute_max_path_sum()
    print(f"\n最大スコア: {max_score}")
    path_finder.display_dp_table()


if __name__ == "__main__":
    main()

まずは、boardインスタンスを生成。boadクラスで入力を受け付けて、盤面を作成している。

class Board:
    def __init__(self):
        self.H, self.W = map(int, input("行と列を入力してください: ").split())
        self.grid = self._read_board()

    def _read_board(self):
        """盤面の読み込み"""
        board = []
        for _ in range(self.H):
            board.append(list(map(int, input().split())))
        return board

以下の入力値。

行と列を入力してください: 4 4
1 1 1 2
1 1 2 2
1 2 2 2
2 2 2 2

次に、path_finderインスタンスを生成している。PathFinderクラスでは、盤面、盤面の高さ、盤面の幅、動的計画法の盤面を初期化している。

class PathFinder:
    def __init__(self, board):
        self.board = board
        self.H = board.H
        self.W = board.W
        self.dp = [[0] * self.W for _ in range(self.H)]

    def compute_max_path_sum(self):
        """動的計画法で最大スコアを求める"""
        self.dp[0] = self.board.grid[0][:]

        for y in range(1, self.H):
            for x in range(self.W):
                candidates = []
                for dx in [-1, 0, 1]:
                    prev_x = x + dx
                    if 0 <= prev_x < self.W:
                        candidates.append(self.dp[y - 1][prev_x])
                self.dp[y][x] = self.board.grid[y][x] + max(candidates)

        return max(self.dp[-1])

    def display_dp_table(self):
        """DPテーブルを可視化"""
        print("\nDPテーブル:")
        for row in self.dp:
            print(*row)

次に、compute_max_path_sumメソッドを使用して、最大スコアを計算している。

def main():
    max_score = path_finder.compute_max_path_sum()
    print(f"\n最大スコア: {max_score}")

class PathFinder:
     def compute_max_path_sum(self):
        """動的計画法で最大スコアを求める"""
        self.dp[0] = self.board.grid[0][:]

        for y in range(1, self.H):
            for x in range(self.W):
                candidates = []
                for dx in [-1, 0, 1]:
                    prev_x = x + dx
                    if 0 <= prev_x < self.W:
                        candidates.append(self.dp[y - 1][prev_x])
                self.dp[y][x] = self.board.grid[y][x] + max(candidates)

        return max(self.dp[-1])

動的計画法で最大スコアを求める

compute_max_path_sumメソッドについて見ていこう。

動的計画法の盤面の1行目は、盤面の最初の行になる。

self.dp[0] = self.board.grid[0][:]

次に、盤面の高さと幅に合わせて、二重ループが回る。

        for y in range(1, self.H):
            for x in range(self.W):
                candidates = []
                for dx in [-1, 0, 1]:
                    prev_x = x + dx
                    if 0 <= prev_x < self.W:
                        candidates.append(self.dp[y - 1][prev_x])
                self.dp[y][x] = self.board.grid[y][x] + max(candidates)

candidatesとは、前の行の値の最大値となり得る値の候補。

candidates = []

前の行の左斜め上、真上、右斜め上からしか来れないという条件が今回あるので、以下のfor文を回す。

                for dx in [-1, 0, 1]:
                    prev_x = x + dx
                    if 0 <= prev_x < self.W:
                        candidates.append(self.dp[y - 1][prev_x])

prev_xは、盤面の現在のX座標に左斜め上、真上、右斜め上の値を足した値になる。

xが一番左（x=0）の時は、prev_xがマイナスになってしまうなどを防ぐために、以下の条件を挟んでいる。

if 0 <= prev_x < self.W:

candidatesには、動的計画法の盤面の一行上かつ、このfor文で決めたprev_xの値が入る。

盤面の現在の値に、このcandidatesの最大値を足した値が、現在の動的計画法の盤面の値となる。

self.dp[y][x] = self.board.grid[y][x] + max(candidates)

累積の値。以前の最大値の累積を使用している。

最終行の最大値を返している。

return max(self.dp[-1])

以下の関数

    def display_dp_table(self):
        """DPテーブルを可視化"""
        print("\nDPテーブル:")
        for row in self.dp:
            print(*row)

で可視化されたDPテーブルはこちら。

DPテーブル:
1 1 1 2
2 2 4 4
3 6 6 6
8 8 8 8