先枚举区间长度，再枚举左端点l,右端点r=l+len-1

1.石子合并

#include <iostream>
using namespace std;
const int maxn=310;
int dp[maxn][maxn];
int a[maxn];
int main(){
    int n;
    cin>>n;
    for(int i=0; i<n; i++)cin>>a[i];
    for(int i=0; i<n; i++)a[i]+=a[i-1];

    for(int len=2; len<=n; len++){
        for(int l=0; l+len-1<n; l++){
            int r=l+len-1;
            dp[l][r]=1e9;
            for(int k=l; k<=r; k++){
                dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+a[r]-a[l-1]);
            }
        }
    }
    cout<<dp[0][n-1];
}

2.密码脱落

#include <iostream>
#include <string>
using namespace std;
const int maxn=1e3+10;
int dp[maxn][maxn];
int main(){
    string a;
    cin>>a;
    int n=a.size();
    for(int len=1; len<=n; len++){
        for(int l=0; l+len-1<n; l++){
            int r=l+len-1;
            if(len==1)dp[l][r]=1;
            else {
                if(a[l]==a[r])dp[l][r]=dp[l+1][r-1]+2;
                if(dp[l+1][r]>dp[l][r])dp[l][r]=dp[l+1][r];
                if(dp[l][r-1]>dp[l][r])dp[l][r]=dp[l][r-1];
            }
        }
    }
    cout<<n-dp[0][n-1];
}