動的計画法

Contents

概要

動的計画法(Dynamic Programming)とは、対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていくアルゴリズムの総称です。

(引用：Wikipedia)

競プロでは組み合わせ数の数え上げや確率、期待値の算出によく使われます。

基本的な考え方は、漸化式を立てて「現状態(及び過去の状態)の値から、次状態の値を算出する」です。

代表的問題

ナップサック問題

ある容量のナップサックに様々な物を入れる時、選んだ物の価値の総和を最大化する問題です。

例題

最長増加部分列の長さ

最長増加部分列(LIS: Longest Increasing Subsequence)とは、数列 Aから任意の個数の整数を取り除き作成できる、単調増加な数列です。

例えば、以下のような数列があった場合を考えてみましょう。

index 0 1 2 3 4 5
value 1 3 4 2 6 5

この配列のLISは「1, 3, 4, 6」となり、LISの長さは4となります。

この長さも、以下のような動的計画法で求めることが可能です。
lower_boundはソート済み配列にしか使用できないので、dp[0]は-INFにすることに注意しましょう。

const long long INF = 1LL << 60;

ll n;
cin >> n;

vll a(n);
rep(i, n) {
  cin >> a[i];
}

vll dp(n + 1, INF);
dp[0] = -INF;

ll ans = 0;
for (const auto& v : a) {
  auto itr = std::lower_bound(all(dp), v);
  *itr = v;
  chmax(ans, (ll)std::distance(dp.begin(), itr));
}

例題

その他

DPのパターン

桁DP

「N以下の正整数で、〇〇を満たす数値の個数を求めよ」といった問題に使うDPです。

最上位桁から1桁ずつ順に走査していき、

  • N未満が確定しているパターン
  • N未満が確定していないパターン

それぞれについてを数え上げていきます。
この「N未満が確定しているか」を未満フラグと言います。

例題

以下はABC154の問題、Almost Everywhere Zeroの解答です。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  string s;
  cin >> s;

  int k;
  cin >> k;

  // 桁数
  int digit = s.size();

  // dp[桁数][k(1〜9を何個含むか)][未満フラグ]
  vector<vector<vector<ll>>> dp(digit + 1, vector<vector<ll>>(k + 2, vector<ll>(2)));

  // 初期条件
  // s[-1]に当たる桁を便宜上0とする。
  // このとき、未満フラグOffの数値が1種類存在することになる。
  dp[0][0][0] = 1;

  for (int d = 0; d < digit; d++) {
    for (int i = 0; i <= k; i++) {
      int D = s[d] - '0';

      for (int h = 0; h <= 9; h++) {
        // この桁を0にする場合
        // 更新対象: dp[d + 1][i][0 or 1]
        if (h == 0) {
          //未満フラグOnのものはそのまま引き継ぎ
          dp[d + 1][i][1] += dp[d][i][1];

          // 未満フラグOffのものの引き継ぎ方を決定
          if (h == D) {
            // 未満フラグOff→Offで引き継ぎ
            dp[d + 1][i][0] += dp[d][i][0];
          } else if (h < D) {
            // 該当桁の値Dが1以上なら未満フラグOff→Onで引き継ぎ
            dp[d + 1][i][1] += dp[d][i][0];
          }
        }
        // この桁を0以外にする場合(kにあたる値が変化する)
        // 更新対象: dp[d + 1][i + 1][0 or 1]
        else {
          // 未満フラグOnのものはそのまま引き継ぎ
          dp[d + 1][i + 1][1] += dp[d][i][1];

          if (h == D) {
            // 未満フラグOff→Offで引き継ぎ
            dp[d + 1][i + 1][0] += dp[d][i][0];
          } else if (h < D) {
            // 未満フラグOff→Onで引き継ぎ
            dp[d + 1][i + 1][1] += dp[d][i][0];
          }
        }
      }
    }
  }

  ll ans = dp[digit][k][0] + dp[digit][k][1];
  cout << ans << endl;
}

関連問題

参考

bit DP

巡回セールスマン問題(TSP)を解くとき等に使えます。

各ノードを2進数の各桁で表し、訪問済みのノードのbitを1、そうでないところを0とします。
例えばdp[5][…]の場合、101bなので「ノード0とノード2を訪問済み」であることを表します。

関連問題

区間DP

関連問題

  • Slimes (Educational DP Contest)

耳DP

集合(A1, A2, … , An)に対し任意の範囲[L, R]を取る問題へのアプローチです。

以下の3種類の状態を作り、適切に遷移することで解きます。

  1. 左端も右端も決定していない状態
  2. 左端は決定済みだが右端は決定していない状態
  3. 右端も決定済みの状態

関連問題

木DP

木に対してDFSしてDPします。

子から得た情報を親に伝播させていくイメージです。

全方位木DP

英語ではRerootingと言われるテクニックです。

Aを根として木DPをした後、その根の子Bに、「Aの場合の数から子Bを除いた情報」を教えることによって、子Bが親だった場合の場合の数を数える事ができます。

参考

関連問題