動的計画法（Dynamic Programming）Vol.1

自己紹介

名前：buridaikon
九州工業大学情報工学部情工2類のものです
　勉強の記録として記事を書いていこうと思います。本当に素人なので、間違っているところがあれば指摘していただけると幸いです。

内容

このページの説明

　ここは動的計画法を用いる問題を集めた記事です。アルゴ式の問題を引用させていただきました。

動的計画法（以下DPと略記）とは何か？

　DPとはアルゴリズム設計技法のひとつです。問題の小さな部分問題を解いていくことで大きな部分の問題を解くことができることを目的としています。

問題

問題「数値の例」

例１

入力例１

6 1 1

出力例１

8

例２

入力例２

31 41 59

出力例２

49

解答

/* 「「　動的計画法　」」*/

#include <bits/stdc++.h>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int n, x, y;
    cin >> n >> x >> y;

    vector<int> vec(n);

    vec[0] = x, vec[1] = y;

    for (int i = 2; i < n; i++) {
        vec[i] = (vec[i-2] + vec[i-1]) % 100;
    }

    cout << vec[n-1] << endl;

    return 0;
}

問題を見ると再帰関数を用いて処理することを考えてしまうかもしれませんが、そうすると計算量が多くなってしまい、TLEになる可能性が高いです。
この問題では、3項間にわたる処理を一つにまとめることで、簡潔にしています。再帰的な求め方ではなく、DPの考え方で工夫をしたため計算量を減らせていることに着目してください。

ここまで読んでいただき、ありがとうございます！
今回はC++のみで記述しましたが、機会があれば他の言語でも解説していきたいと思います
実際に手を動かしてやってみましょう！