区间dp

1.先枚举区间长度

for(int len=3;len<=n;len++){
    for(int i=0;i+len-1<n;i++){
        int j = i+len-1;
        for(int k=i+1;k<=j-1;k++){
            dp[i][j] = max(dp[i][j], a[k]*a[i]*a[j]+dp[i][k]+dp[k][j]);
        }
    }
}

这种比较好理解。

2.先枚举区间边界

for(int i=n-1;i>=0;i--){
    for(int j=i+1;j<=n-1;j++){
        for(int k=i+1;k<=j-1;k++){
            dp[i][j] = max(dp[i][j], a[k]*a[i]*a[j]+dp[i][k]+dp[k][j]);
        }
    }
}

这种方式在枚举左边界的时候需要逆序枚举，因为区间dp要保证所有小区间都被计算过了才能计算大区间，如果i正向枚举的话，会导致dp[k][j]没有被计算过，因为k>i，而反向枚举i即可保证所有的dp[k][j]都被计算过。