problem link: http://usaco.org/index.php?page=viewproblem2&cpid=1114
solutino link: http://usaco.org/current/data/sol_prob2_gold_feb21.html
#include <bits/stdc++.h>
using namespace std;
int N, dp[305][305];
int main() {
cin >> N;
vector<int> a(N);
for (int& t: a) cin >> t;
for (int i = N-1; i >= 0; --i)
for (int j = i+1; j < N; ++j) {
if (a[i] == a[j]) // draw segment from i to j
dp[i][j] = max(dp[i][j],1+dp[i+1][j-1]);
for (int k = i+1; k < j; ++k) // split at k
dp[i][j] = max(dp[i][j],dp[i][k]+dp[k][j]);
}
cout << N-dp[0][N-1] << "\n";
}
i’m confused why the transition is dp[i][j] = max(dp[i][j],dp[i][k]+dp[k][j]); but not dp[i][j] = max(dp[i][j],dp[i][k]+dp[k+1][j]);
any help would be appreciated. Thanks!