01、DP 概述

1. DP 问题的特征

下面以斐波那契数为例说明 DP 的概念。斐波那契数列的每个数字是前面两个数字的和，前几个数是 1、1、2、3、5、8。计算第 n 个斐波那契数，用递推公式进行计算：

fib(n) = fib(n-1) + fib(n-2)

用递归编程，代码如下。

int fib (int n){

    if (n == 1 || n == 2)

        return 1;

    return (fib (n -1) + fib (n -2));

}

为了解决总体问题 fib(n)，将其分解为两个较小的子问题 fib(n−1)和 fib(n−2)。这就是 DP 的应用场景。

有一些问题有 2 个特征：重叠子问题、最优子结构。用 DP 可以高效率地处理具有这 2 个特征的问题。

（1）重叠子问题

首先，子问题是原大问题的小版本，计算步骤完全一样；其次，计算大问题的时候，需要多次重复计算小问题。这就是“重叠子问题”。以斐波那契数为例，用递归计算 fib(5)，分解为以下子问题：

▍图 1 计算斐波那契数

其中 fib(3)计算了 2 次，其实只算 1 次就够了。

一个子问题的多次计算，耗费了大量时间。用 DP 处理重叠子问题，每个子问题只需要计算一次，从而避免了重复计算，这就是 DP 效率高的原因。具体的做法是：首先分析得到最优子结构，然后用递推或者记忆化递归进行编程，从而实现了高效的计算。

需要注意的是，DP 在获得时间高效率的同时，可能耗费更多的空间，即“时间效率高，空间耗费大”。滚动数组是优化空间效率的一个办法。

（2）最优子结构

最优子结构的意思是：首先，大问题的最优解包含小问题的最优解；其次，可以通过小问题的最优解推导出大问题的最优解。在斐波那契问题中，把数列的计算构造成 fib(n)=fib(n−1)+fib(n−2)，即把原来为 n 的大问题，减小为 n−1 和 n−2 的小问题，这是斐波那契数的最优子结构。

在 DP 的概念中，还常常提到“无后效性”，简单地说就是“未来与过去无关”、“过去不影响未来”。此概念不太容易理解，下面以走楼梯问题为例进行解释。

走楼梯问题：一次可以走一个台阶或者两个台阶，问走到第 n 个台阶时，一共有多少种走法？

它的数学模型就是斐波那契数列 fib(n)=fib(n−1)+fib(n−2)。要走到第 n 级台阶，有两种方法，一种是从 n−1 级台阶走一步过来，一种是从 n−2 级台阶走两步过来。但是，前面是怎么走到第 n−1 级，怎么走到 n−2 级台阶，fib(n−1)和 fib(n−2)是如何计算得到的，并不需要知道，只需要它们的计算结果就行了。换句话说，“只关心前面的结果，不关心前面的过程”，在计算 fib(n)的时候，只需要 fib(n)和 fib(n−1)的结果，不需要知道它们的计算过程，这就是无后效性。

无后效性是应用 DP 的必要条件，因为只有这样，才能减少算法的复杂度，应用 DP 才有意义。如果不满足无后效性，那么在计算 fib(n)的时候，还需要重新计算 ffib(n−1)、fib(n−2)，算法并没有优化。

从最优子结构的概念可以看出，它是满足无后效性的。这里用斐波那契数列举例说明 DP 的概念，可能过于简单，不足以说明 DP 的特征。

2. DP 的两种实现

处理 DP 中的大问题和小问题，有两种思路：自顶向下（先大问题再小问题）、自下而上（先小问题再大问题）。

编码实现 DP 时，自顶向下用带记忆化的递归，自下而上用递推。两种方法的复杂度是一样的，每个子问题都计算一遍，而且只计算一遍。

（1）自顶向下与记忆化递归

先考虑大问题，再缩小到小问题，递归很直接地体现了这种思路。为避免递归时重复计算子问题，可以在子问题得到解决时，就保存结果，再次需要这个结果时，直接返回保存的结果就行了。这种存储已经解决的子问题的结果的技术称为“记忆化（Memoization）”。

以斐波那契数为例，记忆化代码如下：

int memoize[maxn]; //保存结果
int fib (int n){
    if (n == 1 || n == 2)
        return 1;
    if(memoize[n] != 0) //直接返回保存的结果，不再递归
        return memoize[n];
    memoize[n]= fib (n - 1) + fib (n - 2); //递归计算结果，并记忆
    return memoize[n];
}

（2）自下而上与制表递推

这种方法与递归的自顶向下相反，避免了递归的编程方法。这种“自下而上”的方法，先解决子问题，再递推到大问题。通常通过填写多维表格来完成。根据表中的结果，逐步计算出大问题的解决方案。

用制表法计算斐波那契数，维护一个一维表 dp[]，记录自下而上的计算结果，更大的数是前面两个数的和。

代码如下：

const int maxn = 255;
int dp[maxn];
int fib (int n){
    dp[1] = dp[2] =1;
    for (int i = 3;i<=n;i++)
        dp[i] = dp[i-1] +dp[i-2];
    return dp[n];
}

在 DP 编程时，大多使用制表递推的编程方法。超过 4 维（ddp[][][][]）的表格也是常见的。

02、经典 DP 面试问题

本节介绍了 10 个经典的 DP 面试问题，并且以第一个“0/1 背包问题”为例，详细解释与 DP 有关的内容：

（1）dp 的设计；

（2）dp 方程的推导；

（3）记忆化和递推编码；

（4）具体方案的输出；

（5）滚动数组。DP 使用的空间可以用滚动数组优化。DP 的状态方程，常常是二维和二维以上，占用了太多的空间。滚动数组是减少空间的技术，例如它可以把二维状态方程的 O(n2)空间复杂度，优化到 O(n)，更高维的数组也可以优化。

1. 0/1 背包问题（0/1 Knapsack Problem）

问题描述：给定 n 种物品和一个背包，物品 i ii 的重量是 wi，价值为 vi，背包的总容量为 C。把物品装入背包时，第 i ii 种物品只有两种选择：装入背包或不装入背包，称为 0/1 背包。如何选择装入背包的物品，使得装入背包中的物品的总价值最大?

设 xi 表示物品 i 装入背包的情况：xi=0 时，不装入背包；xi=1 时，装入背包。有以下约束条件和目标函数：

约束条件：

问题描述：“骨头收集者”带着体积 C 的背包去捡骨头，已知每个骨头的体积和价值，求能装进背包的最大价值。N <= 1000，C<= 1000。

输入：第 1 行是测试数量；后面每 3 行是 1 个测试，其中第 1 行是骨头数量 N 和背包体积 C，第 2 行是每个骨头的价值，第 3 行是每个骨头的体积。

输出：

最大价值。

样例输入：

1

5 10

1 2 3 4 5

5 4 3 2 1

样例输出：

14

（1）dp 的设计

引进一个(N+1)×(C+1)大小的二维数组 dp，dpi表示把前 i 个物品（从第 1 个到第 i 个）装入容量为 j 的背包中获得的最大价值。

可以把每个 dpi都看成一个背包，最后的 dpN就是答案：把 N 个物品装进容量 C 的背包。

（2）dp 转移方程

现在自下而上计算 dp，假设现在递推到 dpi，它表示把前 i 个物品装进容量为 j 的背包。分 2 种情况：

1）第 i 个物品的体积比容量 j 还大，不能装进容量 j 的背包。那么直接继承前 i−1 个物品装进容量 j 的背包的情况即可：dpi =dpi−1。

2）第 i 个物品的体积比容量 j 小，能装进背包。又可以分为 2 种情况：装或者不装第 i 个。

（a）装第 i 个。从前 i−1 个物品的情况下推广而来，前 i−1 个物品是 dpi−1。第 i 个物品装进背包后，背包容量减少 bone[i].volum，价值增加 bone[i].value。所以有：

dpi=dpi−1.volum]+bone[i].value

（b）不装第 i 个。那么 dpi=dpi−1。

取（a）和（b）的最大值，状态转移方程是：

dpi=max(dpi−1,dpi−1.volum]+bone[i].value)

总结上述分析，0/1 背包问题的重叠子问题是 dpi，最优子结构是 dpi的状态转移方程。

算法的时间复杂度：算法需要计算二维矩阵 dp，二维矩阵大小是 N×C，每一项计算时间是 O(1)，总复杂度是 O(N×C)。算法的空间复杂度是 O(N×C)。

0/1 背包问题的简化版。一般物品有体积（或者重量）、价值这 2 个属性，求满足体积约束条件下的最大价值。如果再简单一点，只有一个体积属性，求能放到背包的最多物品，那么，只要把体积看成价值，求最大体积就好了。状态方程变为：

dpi=max(dpi−1,dpi−1]+volum[i])

（3）详解 dp 的转移过程

初学者可能对上面的描述仍不太清楚，下面用一个例子详细说明：有 4 个物品，其体积分别是{2, 3, 6, 5}，价值分别为{6, 3, 5, 4}，背包的容量为 9。

填 dp 表的过程，按照只装第 1 个物品、只放前 2 个、只放前 3 个…的顺序，一直到装完，这就是从小问题扩展到大问题的过程。

▍图 2 dp 矩阵

步骤 1：只装第 1 个物品。

由于物品 1 的体积是 2，所以背包容量小于 2 的，都放不进去，得 dp1=dp1=0；

物品 1 的体积等于背包容量，能装进去，背包价值等于物品 1 的价值，dp1=6；

容量大于 2 的背包，多余的容量用不到，所以价值和容量 2 的背包一样。

▍图 3 装第 1 个物品

步骤 2：只装前 2 个物品。

如果物品 2 体积比背包容量大，那么不能装物品 2，情况和只装第 1 个一样。见下图中的 ddp2=dp2=0，dp2=6。

下面填 dp2。物品 2 体积等于背包容量，那么可以装物品 2，也可以不装：

  （a）如果装物品 2（体积是 3），那么可以变成一个更小的问题，即只把物品 1 装到（容量 - 3）的背包中。

▍图 4 装第 2 个物品

（b）如果不装物品 2，那么相当于只把物品 1 装到背包中。

▍图 5 不装第 2 个物品

取（a）和（b）的最大值，得 dp2=max{3,6}=6。

后续步骤：继续以上过程，最后得到下图（图中的箭头是几个例子）：

▍图 6 完成 dp 矩阵

最后的答案是 dp4：把 4 个物品装到容量为 9 的背包，最大价值是 11。

（4）输出背包方案

现在回头看具体装了哪些物品。需要倒过来观察：

dp4=maxdp3+4,dp3=dp3，说明没有装物品 4，用 x4=0 表示；

dp3=maxdp2+5,dp2=dp2+5=11，说明装了物品 3，x3=1；

dp2=maxdp1+3,dp1=dp1，说明没有装物品 2，x2=0；

dp1=maxdp0+6,dp0=dp0+6=6，说明装了物品 1，x1=1。

图中的实线箭头指出了方案的路径。

▍图 7 背包方案

（5）记忆化代码和递推代码

下面的代码分别用自下而上的递推和自上而下的记忆化递归实现。

  1）递推代码。

#include<bits/stdc++.h>
using namespace std;
struct BONE{
  int value, volum;
}bone[1011];
int dp[1011][1011];
int solve(int n, int c){
    for(int i=1; i<=n; i++)
        for(int j=0; j<=c; j++){
         if(bone[i].volum > j) //第i个物品比背包还大，装不了
              dp[i][j] = dp[i-1][j];
           else                        //第i个物品可以装
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-bone[i].volum]+bone[i].value);
    }
    return dp[n][c];
}
int main(){
  int T; cin>>T;
  while(T--){
    int N,C; cin >> N >> C;
    for(int i=1;i<=N;i++) cin>>bone[i].value;
    for(int i=1;i<=N;i++) cin>>bone[i].volum;
        memset(dp,0,sizeof(dp));
    cout << solve(N, C) << endl;
  }
  return 0;

2）记忆化代码。只改动了上面代码中的 solve()。

int solve(int i, int j){ //前i个物品，放进容量j的背包
    if (dp[i][j] != 0) //记忆化
        return dp[i][j];
  if(i == 0) return 0;
  int res;
  if(bone[i].volum > j) //第i个物品比背包还大，装不了
        res = solve(i-1,j);
  else                           //第i个物品可以装
        res = max(solve(i-1,j), solve(i-1,j-bone[i].volum)+bone[i].value);
    return dp[i][j] = res;
}

（6）滚动数组

上述代码使用了二维矩阵 dp[][]，有可能超过题目许可的空间限制。此时可以用滚动数组减少空间，也就是把 dp[][]替换成一维的 dp[]。观察二维表 dp[][]，可以发现，每一行是从上面一行算出来的，只跟上面一行有关系，跟更前面的行没有关系，那么用新的一行覆盖原来的一行（滚动）就好了。

int dp[1011]; //替换 int dp[1011][1011];
int solve(int n, int c){
    for(int i=1; i<=n; i++)
        for(int j=c; j>=bone[i].volum; j--) //反过来循环
            dp[j] = max(dp[j],dp[j-bone[i].volum]+bone[i].value);
    return dp[c];
}

注意 j 应该反过来循环，即从后面往前面覆盖。请大家思考原因。

经过滚动数组的优化，空间复杂度从 O(N×C)减少为 O(C)。

滚动数组也有缺点。它覆盖了中间转移状态，只留下了最后的状态，所以损失了很多信息，导致无法输出背包的方案。

二维以上的 dp 数组也常常能优化。比如求 dp[t][][]，如果它只和 dp[t−1][][]有关，不需 dp[t−2][][]、dp[t−3][][]等，那么可以把数组缩小为 dp[2][][]。后面的很多问题都可以用滚动数组优化。

2. 最长公共子序列（Longest Common Subsequence，LCS)

一个给定序列的子序列，是在该序列中删去若干元素后得到的序列。例如：X = {A,B,C,B,D,A,B}，它的子序列有{A,B,C,B,A}、{A,B,D}、{B,C,D,B}等。子序列和子串是不同的概念，子串的元素在原序列中是连续的。

给定两个序列 X 和 Y ，当另一序列 Z 既是 X 的子序列又是 Y 的子序列时，称 Z 是序列 X 和 Y 的公共子序列。最长公共子序列是长度最长的子序列。

问题描述：给定两个序列 X 和 Y ，找出 X 和 Y 的一个最长公共子序列。

用暴力法找最长公共子序列，需要先找出 X 的所有子序列，然后验证是否 Y 的子序列。如果 X 有 m 个元素，那么 X 有 2m 个子序列；Y 有 n 个元素；总复杂度大于 O(n2m)。

用动态规划求 LCS，复杂度是 O(nm)。

用 dpi表示序列 Xi（表示 x1,...,xi 这个序列，即 X 的前 i 个元素组成的序列；这里用小写的 x 表示元素，用大写的 X 表示序列）和 Yj（表示 y1,...,yj 这个序列，即 Y YY 的前 j jj 个元素）的最长公共子序列的长度。dpn就是答案。

分解为 2 种情况：

（1）当 xi=yj 时，找出 Xi−1 和 Yj−1 的最长公共子序列，然后在其尾部加上 xi 即可得到 Xi 和 Yj 的最长公共子序列。

（2）当 x i ≠ y j 时，求解两个子问题：Xi−1 和 Yj 的最长公共子序列；Xi 和 Yj−1 的最长公共子序列。取其中的最大值。

状态转移方程是：

dpi=dpi−1+1          xi=yj

dpi=max{dpi,dpi−1}    x i ≠ y j

3. 最长上升子序列（Longest Increasing Subsequence，LIS）

问题描述：给定一个长度为 n nn 的数组，找出一个最长的单调递增子序列。

例如一个长度为 6 的序列 A = { 5 , 6 , 7 , 4 , 2 , 8 , 3 } ，它最长的单调递增子序列为{5,6,7,8}，长度为 4。

定义状态 dp[i]，表示以第 i 个数为结尾的最长递增子序列的长度，那么：

dp[i]=max{dp[j]}+1 0<j<i,Aj<Ai

最后答案是 max{dp[i]}。

复杂度：j 在 0 ~ i 之间滑动，复杂度是 O(n)；i 的变动范围也是 O(n)的；总复杂度 O(n2)。

DP 并不是 LIS 问题的最优解法，有复杂度 O(nlogn)的非 DP 解法[参考本篇参考书《算法竞赛入门到进阶》“7.1.4 最长递增子序列”的详细讲解。]。

4. 编辑距离（Edit Distance）

问题描述：给定两个单词 word1 和 word2，计算出将 word1 转换为 word2 所需的最小操作数。一个单词允许进行以下 3 种操作：（1）插入一个字符；（2）删除一个字符；（3）替换一个字符。

把长度为 m 的 word1 存储在数组 word1[1] ~ word1[m]，长度为 n 的 word2 存储在 wword2[1] ~ word2[n]。不用 word1[0]和 word2[0]。

定义二维数组 dp，dpi表示从 word1 的前 i 个字符转换到 word2 的前 j 个字符所需要的操作步骤，dpm就是答案。下图是 word1=”abcf”，word2=”bcfe”的 dp 转移矩阵。

▍图 8 编辑距离的 dp 矩阵

状态转移方程：

(1)若 word1[i]=word2[j]，则 dpi=dpi−1。例如图中 dp2处的箭头。

(2)其他情况：dpi=min{dpi−1,dpi−1,dpi}+1。例如图中 dp4处的箭头。dpi是它左、左上、上的三个值中的最小值加 1，分别对应以下操作：

  1）dpi−1+1，删除，将 word1 的最后字符删除；

  2）dpi+1，插入，在 word2 的最后插入 word1 的最后字符；

  3）dpi−1+1，替换，将 word2 的最后一个字符替换为 word1 的最后一个字符。

复杂度：O(mn)。

5. 最小划分（Minimum Partition）

问题描述：给出一个正整数数组，把它分成 S1、S2 两部分，使 S1 的数字和与 S2 的数字和的差的绝对值最小。最小划分的特例是 S1 和 S2 的数字和相等，即差为 0。

例如：数组[1,6,11,5]，最小划分是 S1=[1,5,6]，S2=[11]；S1 的数字和减去 S2 的数字和，绝对值是∣11−12∣=1。

最小划分问题可以转化为 0/1 背包问题。求出数组的和 sum，把问题转化成：背包的容量为 sum/2，把数组的每个数字看成物品的体积，求出背包最多可以放 res 体积的物品，返回结果∣res−(sum−res)∣。

1. 行走问题（Ways to Cover a Distance）

问题描述：给定一个整数 n 表示距离，一个人每次能走 1、2、3 步，问走到 n 步，有多少种走法。例如 n = 3，有 4 种走法：{1, 1, 1}、{1, 2}、{2, 1}、{3}。

和爬楼梯问题差不多。爬楼梯问题是每次能走 1 级或 2 级，问走到第 n 级有多少种走法。爬楼梯的解实际上是一个斐波那契数列。

定义行走问题的状态 dp[i]为走到第 i 步的走法数量，那么有：

dp[0]=1，dp[1]=1，dp[2]=2

当 i > 2 时：dp[i]=dp[i−1]+dp[i−2]+dp[i−3]

7. 矩阵最长递增路径(Longest Path In Matrix)

问题描述：给定一个矩阵，找一条最长路径，要求路径上的数字递增。矩阵的每个点，可以往上、下、左、右四个方向移动，不能沿对角线方向移动。

例如矩阵：

9 9 3

7 5 7

3 1 1

它的一个最长递增路径是[1, 3, 7, 9]，长度是 4。

下面给出 2 种解法：

（1）暴力 DFS。设矩阵有 m×n 个点，以每个点为起点做 DFS 搜索递增路径，在所有递增路径中找出最长的路径。每个 DFS 都是指数时间复杂度的，复杂度非常高。

（2）记忆化搜索。在暴力 DFS 的基础上，用记忆化进行优化。把每个点用 DFS 得到的最长递增路径记下来，后面再搜到这个点时，直接返回结果。由于每个点只计算一次，每个边也只计算一次，虽然做了 m×n 次 DFS 搜索，但是总复杂度仍然是 O(V+E)= O(mn)的，其中 V 是点数，E 是边数。这也算是动态规划的方法。

8. 子集和问题 （Subset Sum Problem）

问题描述：给定一个非负整数的集合 S，一个值 M，问 S 中是否有一个子集，子集和等于 M。

例如：S[] = {6, 2, 9, 8, 3, 7}, M = 5，存在一个子集{2, 3}，子集和等于 5。

用暴力法求解，即检查所有的子集。子集共有 2n 个，为什么？用二进制帮忙理解：一个元素被选中，标记为 1；没有选中，标记为 0；空集是 n 个 0，所有元素都被选中是 n 个 1，从 n 个 0 到 n 个 1，共有 2n 个。

用 DP 求解，定义二维数组 dp。当 dpi等于 1 时，表示 S 的前 i 个元素存在一个子集和等于 j 。题目的答案就是 dpn。

用 S[1]～S[n]记录集合 S 的 n 个元素。

状态转移方程，分析如下：

（1）若 S[i] > j，则 S[i]不能放在子集中，有 dpi=dpi−1；

（2）若 S[i] <= j, 有两种选择：

不把 S[i]放在子集中，则 dpi=dpi−1；

把 S[i]放在子集中，则 dpi=dpi−1]。

这 2 种选择，只要其中一个为 1，那么 dpi就为 1。
我们可以用下面的图例进行验证。

▍图 9 子集和问题的 dp 矩阵

如果已经确定问题有解，即 dpn=1，如何输出子集内的元素？按推导转移方程的思路，从 dpn开始，沿着 dp 矩阵倒推回去即可。

9. 最优游戏策略（Optimal Strategy for a Game）

问题描述：有 n 堆硬币排成一行，它们的价值分别是 v1,v2,...,vn，n 为偶数；两人交替拿硬币，每次只能在剩下的硬币中，拿走第一堆或最后一堆硬币。如果你是先手，你能拿到的最大价值是多少？

例如：{8, 15, 3, 7}，先手这样拿可以获胜：（1）先手拿 7；（2）对手拿 8；（3）先手拿 15；（4）对手拿 3，结束。先手拿到的最大价值是 7 + 15 = 22。

这一题不能用贪心法。比如在样例中，如果先手第一次拿 8，那么对手接下来肯定拿 15，先手失败。

定义二维 dp，dpi表示从第 i 堆到 j 堆硬币区间内，先手能拿到的最大值。

在硬币区间[i,j]，先手有两个选择：

  1）拿 i 。接着对手也有 2 个选择，拿 i+1 或 j ：拿 i+1，剩下[i+2,j]；拿 j ,剩下[i+1,j−1]。在这 2 个选择中，对手必然选那个对先手不利的。

  2）拿 j 。接着对手也有 2 个选择，拿 i 或 j−1：拿 i ，剩下[i+1,j−1]；拿 j−1,剩下[i,j−2]。

得到 dp 转移方程：

dpi))dpi=Max(V[i]+min(dpi+2,dpi+1),V[j]+min(dpi+1,dpi))

dpi=V[i]         if j = = i

dpi=max(V[i],V[j])   if j = = i + 1

10. 矩阵链乘法（Matrix Chain Multiplication）

背景知识：

（1）矩阵乘法。如果矩阵 A、B 能相乘，那么 A 的列数等于 B 的行数。设 A 是 m 行 n 列（记为 m×n），B 是 n×u，那么乘积 AB 的行和列是 m×u 的，矩阵乘法 AB 需要做 m×n×u 次乘法计算。（注意本小节的"×"符号有 2 个意思，分别表示矩阵和乘法。）

（2）矩阵乘法的结合律：( A B ) C = A ( B C )。括号体现了计算的先后顺序。

（3）在不同的括号下，矩阵乘法需要的乘法操作次数不同。以矩阵 A、B、C 的乘法为例，设 A 的行和列是 m×n 的，B 是 n×u，C 是 u×v，下面的两种计算方法，需要的乘法次数分别是：

( A B ) C ，计算次数是 m × n × u + m × u × v

A ( B C ) ，计算次数是 m × n × v + n × u × v

两者的差是∣m×n×(u−v)+u×v×(m−n)∣，它可能是一个巨大的值。如果能知道哪一个括号方案是最优的，就能够大大减少计算量。

矩阵链乘法问题：给定一个数组 P[]，其中 p [ i − 1 ] × p [ i ] 表示矩阵 Ai，输出最少的乘法次数，并输出此时的括号方案。

例如 p[] = {40, 20, 30, 10, 30}，它表示 4 个矩阵：40×20，20×30，30×10，10×30。4 个矩阵相乘，当括号方案是( A ( B C ) ) D 时，有最少乘法次数 26000。

如果读者学过区间 DP，就会发现这是一个典型的区间 DP 问题。设链乘的矩阵是 AiAi+1…Aj，即区间[ i , j ] ，那么按结合率，可以把它分成 2 个子区间[ i , k ] 、 [ k + 1 , j ]，分别链乘，有：

AiAi+1…Aj = (Ai...Ak)(Ak+1...Aj)

必定有一个 k ，使得乘法次数最少，记这个 k 为 ki,j。并且记 Ai,j 为此时 AiAi+1…Aj 通过加括号后得到的一个最优方案，它被 ki,j 分开。

那么子链 AiAi+1…Ak 的方案 Ai,k、子链 Ak+1Ak+2…Aj 的方案 Ak+1,j 也都是最优括号子方案。

这样就形成了递推关系：

Ai,j=min{Ai,k+Ak+1,j+pi−1pkpj}

用二维矩阵]dpi来表示]Ai,j，得到转移方程为：

dpi的编码实现，可以套用区间 DP 模板，遍历 i 、 j 、 k ，复杂度是 O(n3)。

区间 DP 常常可以用四边形不等式优化，但是这一题不行，因为它不符合四边形不等式优化所需要的单调性条件。