入门区间DP

Acwing282 石子合并

memset(f,0x3f,sizeof(f));
for(int i = 1; i <= n; i++) cin >> a[i], s[i] = s[i-1]+a[i], f[i][i] = 0; // 读入，初始化
for(int len = 1; len <= n; len++)
    for(int l = 1; l+len-1 <= n; l++) {
        int r = len+l-1;
        for(int k = l; k < r; k++) 
            f[l][r] = min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
    }

环形区间

Acwing1068 环形石子合并

 memset(f,0x3f,sizeof(f));
 for(int i = 1; i <= n; i++) cin >> a[i], a[i+n] = a[i]; // 开两倍
 for(int i = 1; i <= n*2; i++) s[i] = s[i-1]+a[i], f[i][i] = 0;
 for(int len = 1; len <= n; len++) // 所要的长度仍然小于等于n
    for(int l = 1; l + len -1 <= 2*n; l++) {
        int r = l+len-1;
        for(int k = l; k < r; k++) 
            f[l][r] = min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
    }
int ans = 0x3f3f3f3f;
for(int i = 1; i <= n; i++) ans = min(ans,f[i][i+n-1]); // 枚举断点，找到答案

能量项链

Acwing320 能量项链

 // 方法同上

加分二叉树

Acwing479 加分二叉树

 // 枚举根节点，记录每一层状态的根节点
 for(int len = 1; len <= n; len++)
    for(int l = 1; l+len-1 <= n; l++) {
        int r = len+l-1;
        for(int k = l; k <= r; k++) {
            int left = k == l ? 1 : f[l][k-1];
            int right = k == r ? 1 : f[k+1][r];
            int score = left * right + w[k];
            if(score > f[l][r]) {
                f[l][r] = score;
                g[l][r] = k;
            }
        }
    }

// 前序递归遍历输出

void print(int l, int r) {
    if(l > r) return ;
    cout << g[l][r] << " " ;
    print(l,g[l][r]-1);
    print(g[l][r]+1,r);
}