刚看完提高课区间dp还是没搞出来（虽然看出来是区间dp）。惭愧。
这道题边界问题很重要
第一维按长度枚举，从2开始。第二维枚举区间左端点也很正常。第三位一开始很奇怪k为什么从l去到r，这样会有l > r这种情况转移过来。
想通之后发现首先第一点转移过来的是0没有影响。第二点最重要的是一定要这么干。因为左子区间的右端点和枚举的k还有右区间的左端点严格不能相交，但是例如右子区间dp（l + 1, r）是一定要有的，这样k和左子区间就被挤到左边去了，但是由于是0对结果没有影响。

题目描述

正N边形内连边（给01矩阵），求出最多不相交的边数（包括端点相交）

样例

输入
6
0 0 0 1 0 0
0 0 0 0 1 1
0 0 0 0 1 1
1 0 0 0 0 0
0 1 1 0 0 0
0 1 1 0 0 0

输出
2

算法

(区间dp) $O(n^3)$

C++ 代码

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

int n;
int v[505][505];
int dp[505][505];

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    memset(dp, 0, sizeof(dp));
    cin >> n;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) cin >> v[i][j];
    for (int len = 2; len <= n; ++len)
        for (int l = 1; l + len - 1 <= n ; ++l){
            int r = l + len - 1;
            for (int k = l; k <= r; ++k) {
                dp[l][r] = max(dp[l][r], dp[l + 1][k - 1] + v[l][k] + dp[k + 1][r]);
            }
        }
                cout << dp[1][n];
    return 0;
}