区间动态规划

所谓区间dp，指在一段区间上进行动态规划，一般做法是由长度较小的区间往长度较大的区间进行递推，最终得到整个区间的答案，而边界就是长度为1以及2的区间。

转移方程

区间dp常见的转移方程如下：

dp(i,j) = min{dp(i,k-1) + dp(k,j)} + w(i,j)   (i < k <= j)
1

1. $dp(i,j)$ 表示处理从第 $i$ 个元素到第 $j$ 个元素（包括这两个元素）的子序列所需的最小代价或者最优值。这个代价或者最优值是由两部分组成的：一个是分割后的子区间的最优解之和，另一个是处理整个区间 $[i,j]$ 本身的代价或者收益 $w(i,j)$。

2. $mindp(i,k-1)+dp(k,j)$ 这部分是核心，表示对于任意的分割点 $k$，你都将原始的区间 $[i,j]$ 分割成两个小区间 $[i,k-1]$ 和 $[k,j]$，并对这两个小区间分别求解，然后取所有可能的分割方法中最优值的那一个。这个最优值可能来自任意一个分割点 $k$。

3. $w(i,j)$ 是处理完整区间 $[i,j]$ 的直接代价或者收益。这个代价或者收益通常取决于具体问题的设置，例如在一些字符串问题中，$w(i,j)$ 可能代表将子字符串 $[i,j]$ 转换成某种特定状态的代价。

4. $(i<k<=j)$ 确保了分割点 $k 总是位于区间 $(i,j)$ 内部，确保了区间至少被分成两部分，防止了空区间的产生，这有助于避免无效的递归或者无意义的计算。

通过这样的方式，问题就被分解成了多个更小的问题，我们通过计算和比较所有可能的分割方法来找到最优解。这个过程通常通过两层循环（一层遍历所有可能的区间，另一层遍历所有可能的分割点）加上递归或者动态规划的方式来实现。

实例代码：

def calculate_w(i, j):
    # 这个函数应该根据问题的具体情况来定义
    # 它代表了处理从i到j这个区间的直接代价
    return 0  # 这里暂时假设为0，你需要根据实际情况进行修改

def interval_dp(n):
    # 初始化动态规划数组
    dp = [[float('inf')] * n for _ in range(n)]
    
    # 基本情况，通常是长度为1的区间
    for i in range(n):
        dp[i][i] = 0  # 或根据问题的具体情况进行初始化
    
    # 枚举区间长度len从2开始
    for len in range(2, n + 1):
        # 枚举区间起点i
        for i in range(n - len + 1):
            # 计算区间终点j
            j = i + len - 1
            # 枚举分割点k，并更新dp[i][j]
            for k in range(i + 1, j + 1):  # 注意k是从i+1开始的，确保区间至少被分成两部分
                dp[i][j] = min(dp[i][j], dp[i][k - 1] + dp[k][j] + calculate_w(i, j))
    
    # 返回整个序列的最优解
    return dp[0][n - 1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

len因为要把数组分成两个部分，而因为一边的长度最少为1，所以是从2开始。

例题

https://www.luogu.com.cn/problem/P1775

#include <bits/stdc++.h>
using namespace std;
int dp[1100][1100],p[1100],n,a[1100];
int sum(int l,int r){
	return p[r] - p[l-1];
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i = 1; i <= n; i++){
		cin>>a[i];
		p[i] = a[i]+p[i-1];
	}
	for(int i = 1; i <= n; i++) dp[i][i] = 0;
	for(int len = 2; len <= n+1; len++){
		for(int i = 1; i <= n; i++){
			int j = i+len-1;
			if(j > n) break;
			dp[i][j] = INT_MAX;
			for(int k = i+1; k <= j+1; k++){
				dp[i][j] = min(dp[i][j],dp[i][k-1]+dp[k][j]+sum(i,j));
			}
		}
	}
	cout<<dp[1][n]<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28