DEV

C++ 区間DP

#C++#アルゴリズム

参考： 区間DPを勉強してみた - Kutimotiの競プロメモ

区間DPとは何かと言われるといまいちよく分からないが、上記に書いてあることの仕組みは大体分かった。でもまだボトムアップ型のコードしか見てないけど。ナップサック問題と似ていて、細切れにして計算しておき、全体の計算量を減らしている。細切れの計算から始めて徐々に計算範囲を広げて、最後に本当に知りたい答えに行き着くのが、ボトムアップ型。再帰型は、多分全体を知りたいという関数を実行すると、勝手にボトムの計算をメモりながら再帰的に行う。新しい問題で解き方思いつけるのか謎。。

上記のダルマさん問題のボトムアップ式コードでは、全消し可能かを確認しつつ、対象範囲を全パターンで区切って消せる最大数を取得している。徐々に対象範囲を広げることで、区切った際に確実に消せる最大数が既に分かってる状態が作れる。

なにしろDPは、細分化して覚えておくやつのことなんだなーと思った。

ダルマさん問題のサンプルコード（ボトムアップ版）

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;


void daruma(pair<int, vector<int>> dataset)
{
  int n;
  vector<int> w;
  tie(n, w) = dataset;
  vector<vector<int>> dp(n, vector<int>(n, 0));
  for (int W = 2; W <= n; W++)
  {
    for (int l = 0; l < n; l++)
    {
      int r = l + W - 1;
      if (r >= n)
        continue;


      if (dp[l + 1][r - 1] == W - 2 && abs(w[l] - w[r]) <= 1) {
        dp[l][r] = W;
      } else {
        for (int mid = l; mid < r; mid++)
        {
          dp[l][r] = max(dp[l][r], dp[l][mid] + dp[mid + 1][r]);
        }
      }
    }
  }
  cout << dp[0][n - 1] << endl;
}


int main()
{
  vector<pair<int, vector<int>>> dataset;
  while (1)
  {
    int n;
    cin >> n;
    if (n < 1)
      break;
    vector<int> w(n);
    for (int i = 0; i < n; ++i)
    {
      cin >> w[i];
    }
    dataset.push_back(make_pair(n, w));
  }
  for (int i = 0; i < dataset.size(); ++i)
  {
    daruma(dataset.at(i));
  }
}