参考: 区間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)); } }