本文共 1772 字，大约阅读时间需要 5 分钟。
???0?1??????????????????????????????????????????????????????????????
??dp[l][r]????[l, r]??????????????????????????dp[l][l] = 0??????????????
?????l??????????????????n???????????????????????
????????????????????????????????
#includeusing namespace std;typedef long long ll;int n, dp[501][501], a[501];const int INF = 0x3f3f3f3f;void dfs(int l, int r) { if (l > r) return 1; if (l == r) return dp[l][r] = 1; if (dp[l][r] != INF) return dp[l][r]; int ans = INF; if (a[l] == a[r]) { ans = dp[l+1][r-1]; if (ans == INF) { ans = dfs(l+1, r-1); } } else { ans = min(dp[l+1][r], dp[l][r-1]); if (ans == INF) { ans = min(dfs(l+1, r), dfs(l, r-1)); } } if (ans != INF) { dp[l][r] = ans; } else { dp[l][r] = INF; } return dp[l][r];}int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); } for (int i = 1; i <= n; ++i) { dp[i][i] = 1; } for (int len = 2; len <= n; ++len) { for (int l = 1; l + len - 1 <= n; ++l) { int r = l + len - 1; if (a[l] == a[r]) { dp[l][r] = dp[l+1][r-1]; } else { dp[l][r] = min(dp[l+1][r], dp[l][r-1]); } if (dp[l][r] > 1) { dp[l][r] = INF; } } } printf("%d", dp[1][n]);}
??????????????????????????????????????????
转载地址：http://sgewz.baihongyu.com/