区间 DP 基础

什么是区间 DP, 区间 DP 特征

区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。令状态 $f(i, j)$ 表示将下标位置 到 的所有元素合并能获得的价值的最大值，那么 $f(i, j) = max{f(i, k) + f(k + 1, j) + cost}, cost$ 为将这两组元素合并起来的代价。

区间 DP 的特点：

合并：即将两个或多个部分进行整合，当然也可以反过来；

特征：能将问题分解为能两两合并的形式；

求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。

这里给出两道例题进行具体分析: 矩阵连乘问题，石头合并问题

矩阵连乘

题目描述：

矩阵 $ [A_1,A_2,…,A_n ]$，其中，$A_i$ 与 $A_{i+1}$ 是可乘的，$(i = 1, 2,…, n-1)$。用加括号的方法表示矩阵连乘的次序，不同的计算次序计算量（乘法次数）是不同的，找出一种加括号的方法，使得矩阵连乘的次数最小。

这里我们要先知道 ：$m * n$ 的 $A$ 矩阵 和 $n * k$ 的 $B$ 矩阵的乘法运算次数为：$m * n * k$

以$A_1 A_2 A_3$ 三个矩阵相乘为例，乘法的顺序可以是 $(A_1 * A_2) * A_3$ 或者是 $A_1 * (A_2 * A_3)$ 这两种顺序的计算量是可能会不同的，所以矩阵的相乘顺序是会影响连乘的次数。

先设 $m[i][j]$ 是矩阵 $A_i - A_j$ 的最小相乘次数。
那对于 $A_i - A_j$，可以将其拆分为 $A_i - A_k，A_{k+1} - A_j (i <= k < j) $ 我们只需要找到这么一个 $k$ 使得以 $k$为分割点所拆分出来的两部分的结果相乘使得 $m[i][j]$ 最小
则$m[i][j] = m[i][k] + m[k + 1][j] + p_{i-1} * p_k * p_j$，那么就将原问题拆解为分别求 $A_i - A_k$ 和 $A_{k+1}－ A_j $的矩阵相乘的最少相乘次数，那么我们就可以得到这样的递推公式

在这里插入图片描述

这里我们采用第底向上的方式：
我们根据

在这里插入图片描述

发现，若是想要计算 $m[i][j]$，就必须先计算出 i 和 j 中的每一个 k 的 $m[i][k] ,m[k +1][j]$，所以就从最小的连乘单元：2个矩阵连乘开始进行计算，而且所有的被分割的子序列，长度都会小于 $j - i +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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>

using namespace std;

const int size = 105;

int m[size][size],s[size][size];//m[i][j]的值是i - j的最小乘数，s[i][j]则是记录过程
int p[size];//存储矩阵的第一个行和中间矩阵的列数以及最后一个矩阵的列

void Min_matrix(int n){
    for(int l = 2; l <= n; l++){//矩阵连乘的单元规模
        for(int i = 1; i <= n - l + 1; i++){//对不同规模的矩阵连乘单元,确定共有多少单元
            int j = i + l - 1;
            m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];//先赋一个初值,以进行下面的比较
            s[i][j] = i;//i - j 的最小相乘次数的决策点
            for(int k = i + 1; k < j; k++){//通过遍历中间点来找到最优决策点
                int temp = m[i][k] + m[k + 1][j] + p[i - 1]*p[k]*p[j];
                if(m[i][j] > temp){
                    m[i][j] = temp;
                    s[i][j] = k;
                }
            }
        }
    }
}

void Print_matrix(int i,int j){//递归打印每次的决策点
    if(i == j){
        cout<<"A["<<i<<"]";
        return ;
    }
    cout<<"(";
    Print_matrix(i,s[i][j]);//这里是递归i - j的每一个决策点，，这里是向左打印
    Print_matrix(s[i][j] + 1,j);//向右打印
    cout<<")";
}

int main()
{
    int n;
	cout<<"请输入矩阵的个数n : "<<endl;
	cin>>n;
	int i,j;
	cout<<"请依次输入每个矩阵的行数和最后一个矩阵的列数："<<endl;
	for(i=0;i<=n;i++)
		cin>>p[i];
	Min_matrix(n);
	Print_matrix(1,n);
	cout<<endl;
	cout<<"最小计算量的值为："<<m[1][n]<<endl;

	return 0;
}

石子合并问题:

跟上面矩阵相乘的思想很接近，不过由于是相邻的石头相加，运算方式不同，思路跟上面一样，这里只给出递推公式
$f[i] [j]$：代表合并第i到第j个石头的最小花费

$sum [ i ]$：表示 $1 –> i$ 个石头的权值之和

$f[i, j]= min{ f[i, k] + f[k + 1, j] + sum[i, j] - sum[i] + a[i]}$

至于为什么是 $sum [ j ]-sum [ i ]+a[i]$，从第 i 个石头到第 j 个石头进行合并的花费就是第i到第j个石头的权值合。

练习题目: