区间DP

石子的合并

思路：

核心：最后一次合并一定是左边连续的一部分和右边连续的一部分进行合并

状态表示：f[i][j]表示将i到j合并成一堆的方案的集合，属性为Min

状态计算：

（1）i<j时， $\underset {i\leq k < j}{min}(f[i][j], f[i][k] + f[k + 1][j]) + s[j] - s[i - 1]$

（2）i==j时， $f [i] [j] = 0$ （合并一堆石子的代价为0）

问题答案：f[1][n]

区间DP常用模板

所有的区间dp问题，第一维都是枚举区间长度，一般len = 1用来初始化，枚举从len = 2开始，第二维枚举起点i（右端点j自动获得，j = i + len - 1）

for(int i = 1; i <= n; ++i){
    dp[i][i] = 初始值
}

for(int len = 2; len <= n; ++len){			// 区间长度
    for(int i = 1; i + len - 1 <= n; ++i){	// 区间起点
        int j = i + len - 1;				// 区间终点
        for(int k = i; k < j; ++k){			// 枚举分割点，构造状态转移方程
            dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);
		}
    }
}

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include <vector>

using namespace std;

const int N = 310, INF = 0x3f3f3f3f;
/*
f[i][j] : 表示第i堆石子到第j堆石子合并的总代价
要合并从i到j堆石子，最后的状态是合并两堆石子，即f[i][j] = f[i][k] + f[k + 1][j] + s[j] - s[i - 1]
初始化状态：f[i][i] = 0; 表示合并第i堆石子的代价是0.
*/
int n, w[N], f[N][N];
int s[N];

int main(){
    scanf("%d", &n);
    
    for(int i = 1; i <= n; ++i){
        scanf("%d", &w[i]);
        s[i] += s[i - 1] + w[i];
    }
    memset(f, 0x3f, sizeof f);
    
    for(int i = 1; i <= n; ++i) f[i][i] = 0;
    
    for(int len = 2; len <= n; ++len){
        for(int i = 1; i + len - 1 <= n; ++i){
            int j = len + i - 1;
            
            for(int k = i; k < j; ++k){
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
            }
        }
    }
    
    printf("%d\n", f[1][n]);
    return 0;
}

记忆化搜索

#include <iostream>
#include <cstring>

using namespace std;

const int N = 307;

int a[N], s[N];
int f[N][N];

// 记忆化搜索：dp的记忆化递归实现
int dp(int i, int j) {
    if (i == j) return 0; // 判断边界
    int &v = f[i][j];

    if (v != -1) return v;

    v = 1e8;
    for (int k = i; k <= j - 1; k ++)
        v = min(v, dp(i, k) + dp(k + 1, j) + s[j] - s[i - 1]);

    return v;
}

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        s[i] += s[i - 1] + a[i];
    }

    memset(f, -1, sizeof f);

    cout << dp(1, n) << endl;


    return 0;
}