DP on Subarrays
DP on subarrays (also called interval DP / range DP) is used when the answer for a segment can be computed from answers of smaller segments inside it. A very typical state is:
This shows up when you “build” a segment by splitting it into two smaller parts, or when you expand from shorter intervals to longer ones.
Define for .
Usually:
Split interval at :
Where depends on the problem (sum, max, min, etc.).
Compute by increasing length:
Problem: Given a string , find the length of the longest subsequence that is a palindrome.
Let = LPS length in substring .
time, memory (can optimize to , but keep it simple).
Problem: Array . Two players alternately take either leftmost or rightmost element. Both play optimally. Find the maximum score the first player can achieve.
Work with score difference:
Then:
Problem: Given array . You can merge only adjacent segments. Merging and costs . Find the minimum total cost to merge everything into one pile.
Let = minimum cost to merge subarray into one pile.
Base:
Transition:
Use prefix sums to compute in .
Total complexity will b .
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
int n = (int)s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) dp[i][i] = 1;
for (int len = 2; len <= n; len++) {
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
if (s[l] == s[r]) {
dp[l][r] = 2 + (l + 1 <= r - 1 ? dp[l + 1][r - 1] : 0);
} else {
dp[l][r] = max(dp[l + 1][r], dp[l][r - 1]);
}
}
}
cout << dp[0][n - 1] << "\n";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
long long sum = 0;
for (int i = 0; i < n; i++) { cin >> a[i]; sum += a[i]; }
vector<vector<long long>> dp(n, vector<long long>(n, 0));
for (int i = 0; i < n; i++) dp[i][i] = a[i];
for (int len = 2; len <= n; len++) {
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
dp[l][r] = max(a[l] - dp[l + 1][r], a[r] - dp[l][r - 1]);
}
}
long long diff = dp[0][n - 1];
long long first = (sum + diff) / 2;
cout << first << "\n";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n + 1), pref(n + 1, 0);
for (int i = 1; i <= n; i++) {
cin >> a[i];
pref[i] = pref[i - 1] + a[i];
}
auto sum = [&](int l, int r) -> long long {
return pref[r] - pref[l - 1];
};
const long long INF = (1LL << 60);
vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, INF));
for (int i = 1; i <= n; i++) dp[i][i] = 0;
for (int len = 2; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
long long add = sum(l, r);
for (int k = l; k < r; k++) {
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + add);
}
}
}
cout << dp[1][n] << "\n";
return 0;
}