Max値取得｜動的計画法( DP ) - C++競プロ学習日記(仮)

動的計画法 ( DP )の学習として解きました。
例題のねらい：動的計画法におけるメモ配列とDPテーブルの違いを確認する。

問題： $N$ 要素の int 型配列 $A$ が与えられる． $A$ の最大値を DP で求めよ

問題制約は特になかったので、適当に。( $1 \leq N \leq 10^6$ くらい？)

1. メモ化再帰編

解の再帰的定義

　 $N$ 個の値の中から最大値を返す関数 $\mathrm rec(n)$ を定義します。

$\begin{equation} 　\mathrm rec(1) = A_0\\ 　\mathrm rec(n)= \max\{\mathrm rec( n - 1 ),\: A_{n-1}\}　( 1 < n)\\ \end{equation}$

正当性の証明

$N = 1$ のとき
1 以下の要素は 1 つしかない為、最大値は $A_0$ となる。
$N > 1$ のとき
配列 $A_{n-1}$ までの最大値が求まると仮定すると、 $A_{n-1}$ までの最大値と $A_n$ を比較すれば、 $A_n$ までの最大値が求まり、よって任意の自然数 $N$ について $\mathrm rec(N)$ は、配列 $A$ から最大値を求める再帰関数として成立する。

計算量

main 関数は std::vector::resize に $O(N)$ 、再帰関数の呼び出しに $O(1)$ 時間。
rec 関数は、訪問済判定の if 文、訪問済だった場合、memo した値を返すのにそれぞれ $O(1)$ 時間。
基底ケース部分は、 if 文、res を返すのにそれぞれ $O(1)$ 時間。再帰ケース部分は std::max *1 を使って大小比較 1 回につき $O(1)$ 時間かかり、それを再帰関数で $N$ 回繰り返すので $O(N)$ 時間。プログラム全体では $O(N)$ 時間。

コード

vector<int> memo( 100000 + 1, -1 );
int N, res;
vector<int> A;
int rec( int i )
{
    int &res = memo[ i ];
    if( res != -1 )
    {
        return res;
    }
    //基底ケース
    if( i == 1 )
    {
        return res = A[ 0 ];
    }
    //再帰ケース
    return res = max( rec( i - 1 ), A[ i - 1 ] );
}
int main()
{
    cin >> N;
    A.resize( N );
    for( auto &x : A )
    {
        cin >> x;
    }
    cout << rec( N ) << endl;
    return 0;
}

実行コード：[Wandbox]三へ( へ՞ਊ ՞)へﾊｯﾊｯ

2. Loop DP 編

　次にメモ化再帰編を元に Loop DP 版を書きました。

計算量

DP 部分は std::max を使っての大小比較 1 回につき $O(1)$ 時間を loop で $N - 1$ 回繰り返すので、 $O(N)$ 時間。
プログラム全体では $O(N)$ 時間となる。

int main()
{
    int N;
    cin >> N;
    vector<int> A( N );
    for( auto &x : A )
    {
        cin >> x;
    }
    vector<int> dp( 100000 + 1 );
    dp[ 1 ] = A[ 0 ];
    for( int i = 2; i <= N; i++ )
    {
        dp[ i ] = max( dp[ i - 1 ], A[ i - 1 ] );
    }
    cout << dp[ N ] << endl;
    return 0;
}

実行コード：[Wandbox]三へ( へ՞ਊ ՞)へﾊｯﾊｯ

3. 学習まとめ

メモ化再帰も loop DP も計算結果を保存して次の計算に使うという本質的な所は同じで、単に実装方法が異なるだけということが例題から良く判りました(おわり)

*1:max - C++ Reference