超基礎的な動的計画法について

はじめに

動的計画法ってあまり優しくなさそうですよね。
なんかナップサック問題とかに関わるらしいくらいの認識の人もいると思います。
そこで、今回はもっと簡単な例を挙げていきます。

最小値の計算

さて、みなさん数列の最小値を計算するときどのような処理をしているでしょうか？

バブルソートなどでソートし先頭をとる

計算量は$${O(N^2)}$$です。
計算量が重いため、正直これをやる人はあまりいないと思います。

#include <iostream>
#include <vector>
using namespace std;

long long int N;
int main() {
    cin>>N;
    vector<long long int>A(N);
    for (long long int i = 0; i < N; i++)
    {
        cin>>A[i];
    }
    for (long long int i = 0; i < N; i++)
    {
        for (long long int j = 0; j < N; j++)
        {
            if(A[j]>A[j+1]){
                swap(A[j],A[j+1]);
            }
        }        
    }
    cout<<A[0]<<endl;
}

std::sortなどでソートし先頭をとる

計算量は$${O(N\log N)}$$です。
計算量についてもそこまで問題がないため、これは僕もよく使います。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long int N;
int main() {
    cin>>N;
    vector<long long int>A(N);
    for (long long int i = 0; i < N; i++)
    {
        cin>>A[i];
    }
    sort(A.begin(),A.end());
    cout<<A[0]<<endl;
}

現在までの最小値を持つ変数を用意して更新

計算量は$${O(N)}$$です。
実装も全然重くありません。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long int N,memo=1e18;//初期値クソデカ
int main() {
    cin>>N;
    vector<long long int>A(N);
    for (long long int i = 0; i < N; i++)
    {
        cin>>A[i];
        memo=min(memo,A[i]);
    }
    cout<<memo<<endl;
}

これを動的計画法として捉えていきましょう。

動的計画法として捉える

先ほどと同じです。
考え方：$${N}$$項からなる数列$${A_i}$$が存在します。先頭から$${i}$$項までの最小値を$${dp_i}$$とすると、$${dp_i}$$は以下のように遷移します。

$$
\begin{align}
&dp_0=A_0\\
&dp_i=\min(dp_{i-1},A_i)\ \ \ …(i\ge 1)
\end{align}
$$

これは明らかに全体の問題を解くために部分問題を解いていおり動的計画法と言えます。これを実際にコードに起こしたものが以下のものになります。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long int N;
int main() {
    cin>>N;
    vector<long long int>A(N),dp(N,1e18);//初期値クソデカ
    for (long long int i = 0; i < N; i++)
    {
        cin>>A[i];
    }
    dp[0]=A[0];
    for (long long int i = 1; i < N; i++)
    {
        dp[i]=min(dp[i-1],A[i]);
    }
    cout<<dp[N-1]<<endl;
}

最後に

普通に行っていた最小値の計算が実は動的計画法だったと思うと何か動的計画法が身近なものに感じられそうではないですか？(感じられなかったらごめんなさい)
皆さんも動的計画法と仲良くなりましょう！

余談

動的計画法が難しい理由の一つに多次元配列の利用が上がると思います。
今回の最小値の計算について各$${i}$$について$${1}$$つのデータしか持っていませんでしたが、ナップサック問題では基本的に二次元配列を使い、各$${i}$$について容量$${W}$$程度のデータを持つこととなります。
これは遷移の際に$${i}$$について容量$${x}$$以下を使用したときの最大価値をそれぞれ持つ必要があるからなのですが、慣れるまで配列から配列に遷移というのは難しいのかなというお気持ちがあります。