DP(動的計画法：Dynamic Programming)とは？

DPとは？

Dynamic Programmingとはアルゴリズムの一種で、一度計算した部分問題の結果を保存(メモ)し再利用することで、効率的に問題を解く手法です。

分かりやすい解説イメージを見つけました、ぜひ一度見て頂きたいです。

https://www.momoyama-usagi.com/entry/info-algo-dp#:~:text=説明しましょう。-,動的計画法のイメージ,-例えば、
うさぎでもわかるアルゴリズム　動的計画法

問題

LeetCodeより引用。
※これより先は考え方とコードが書かれています。

https://leetcode.com/problems/triangle/description/
LeetCode 120. Triangle

三角形の配列が与えられたとき、上から下(下から上)へのパスの和の最小値を返す。
※解説は下から上で行います。
Input: triangle = [[-1],[5,4],[1,-1,-3]]
Output: 0

考え方

1. 最下層から探索を始めます。
2. 最下層の2組から小さい値を見つけます。
3. 一つ上の層をみて計算を行い、メモを残します。
4. 1～3を頂点まで繰り返します。

以下に考え方のgifを示します。

プログラムコード

SolutionクラスのminimumTotalにDPアルゴリズム、
mainはminimumTotalを呼び出して表示します。
以下にコードを示します。

ソースコード.cpp

#include <iostream>
#include <vector>
#include <algorithm>

class Solution {
public:
    int minimumTotal(std::vector<std::vector<int>>& triangle) {
        // 元のtriangleを壊さないため
        std::vector<std::vector<int>> copyTriangle(triangle.size());
        std::copy(triangle.begin(), triangle.end(), copyTriangle.begin());

        // DP処理
        for (int row = copyTriangle.size() - 2; row >= 0; row--)
        {
            for (int column = 0; column < copyTriangle.at(row).size(); column++)
            {
                copyTriangle.at(row).at(column) += std::min(copyTriangle.at(row + 1).at(column), copyTriangle.at(row + 1).at(column + 1));
            }
        }
        return copyTriangle[0][0];
    }
};

int main()
{
    Solution s;
    std::vector<std::vector<int>> a;
    a = {
        {-1},
        {5,4},
        {1,-1,-3},
    };
    std::cout << s.minimumTotal(a) << std::endl;

    return 0;
}

以下に実行結果を示します。

0

コード解説

1. 1つ目のfor文は常に1つ上を見て、上方向に探索を行います。
2. 2つ目のfor文は1つ目のfor文を右方向に移動します。
3. copyTriangle.at(row).at(column)はメモする場所です。
4. copyTriangle.at(row + 1).at(column)は1つ目のfor文より一つ下を指します。
5. copyTriangle.at(row + 1).at(column + 1)は4.の一つ右を指します。

文章での説明は難しいのでgifを示します。