矩阵【DP】【记搜】

题目大意：
N$N$个矩阵相乘，求进行乘法的最少次数，我们认为两个矩阵A(m×n)×B(n×p)$A(m\times n)\times B(n\times p)$的乘法次数为m×n×p$m\times n\times p$次。

Input$Input$

3
50 10
10 20
20 5

Output$Output$

3500

---

思路：
考试时这道题是第一题，推了半天没搞懂，样例也看不懂。总以为正确答案是50×10×20×5=50000$50\times 10\times 20\times 5=50000$。
但是并不是这样的。
我们设第2$2$到n+1$n+1$行的输入数据为a[i]$a[i]$和b[i]$b[i]$，那么我们必须先证明b[i]=a[i+1]$b[i]=a[i+1]$

证明：
根据矩阵乘法的性质，矩阵A*矩阵B 不等于 矩阵B*矩阵A，那么我们能确定，A*B*C不等于A*C*B，
那么题目又说输入确保能够相乘，所以b[i]=a[i+1]。
证毕。

那么再根据A(m×n)×B(n×p)=C(m×p)$A(m\times n)\times B(n\times p)=C(m\times p)$，所以我们可以利用矩阵乘法可以用乘法结合律的特点，将A(m×n)×B(n×p)×C(m×p)$A(m\times n)\times B(n\times p)\times C(m\times p)$变成(A(m×n)×B(n×p))×C(m×p)$(A(m\times n)\times B(n\times p))\times C(m\times p)$,两两相乘，就可以求出正确答案。

那么如何求最小值呢？

有两种方法求最小值，分别指区间DP和记搜，这里就介绍DP的方法。

可以用f[i][j]$f[i][j]$表示矩阵i$i$到矩阵j$j$都被合并的最小值，再从i$i$到j$j$中枚举k$k$，将矩阵分为两边（类似Floyd$Floyd$思想，i$i$到j$j$最短路就枚举其他点k$k$，f[i][j]=min(f[i][j],f[i][k]+f[k][j])$f[i][j]=min(f[i][j],f[i][k]+f[k][j])$），再加上题目给出的A(m×n)×B(n×p)$A(m\times n)\times B(n\times p)$要乘m×n×p$m\times n\times p$次，即a[i]×a[k+1]×b[j]$a[i]\times a[k+1]\times b[j]$（a[k+1]=b[k]$a[k+1]=b[k]$，已经证过，所以也可以是a[i]×b[k]×b[j]$a[i]\times b[k]\times b[j]$）。完整方程如下：

f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+a[i]*a[k+1]*b[j]);

即

f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+a[i]*b[k]*b[j]);

那么i$i$，j$j$，k$k$分别该怎么枚举呢？

不难想到，由于是矩阵i$i$到矩阵j$j$，所以必然有i⩽j$i⩽j$，所以j$j$就要从2枚举到n$n$。（1不能枚举，因为如果枚举了1，i$i$就⩽$⩽$0，明显不成立）。那么根据i⩽j$i⩽j$，也可以推出i$i$要从j−1$j-1$枚举到1。这里必须要倒着枚举，如果从1开始枚举的话，a[i][j]$a[i][j]$里面没有任何一个区间求出最小值，就无法转移。那么k$k$就很简单了，如上文所述，有i⩽k$i⩽k$＜j$j$，所以k自然就在i$i$到j$j$中枚举了。

那么还有最后一个问题：怎么初始化？

由于要求最小值，所以很容易想到要讲f$f$数组全部赋值为INF$INF$，但是。。。

f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+a[i]*a[k+1]*b[j]);

设m=a[i]×a[k+1]×b[j]$m=a[i]\times a[k+1]\times b[j]$，再带入方程，发现。。。

f[i][j]=min(INF,INF+INF+m)

即

f[i][j]=min(INF,INF)

即

f[i][j]=INF

怎么回事？

再仔细想一想，f[i][i]$f[i][i]$这个矩阵的值不可能是INF$INF$，因为它是它本身，所以f[i][i]=0$f[i][i]=0$。

那么当i=j−1$i=j-1$ ，k=i$k=i$时，

f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+a[i]*a[k+1]*b[j]);

即

f[i][j]=min(INF,f[i][i]+f[i+1][j]+m);

即

f[i][j]=min(INF,f[i][i]+f[j][j]+m);

即

f[i][j]=min(INF,0+0+m);

即

f[i][j]=min(INF,m);

即

f[i][j]=m;

所以答案也出来了：从矩阵1乘到矩阵n$n$，即f[1][n]$f[1][n]$。

---

代码：

#include <cstdio>
#include <iostream>
using namespace std;

const int inf=99999999;
int n,a[1001],b[1001],f[601][601];

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
     scanf("%d%d",&a[i],&b[i]);
    for (int i=1;i<=600;i++)
     for (int j=1;j<=600;j++)  //初始化
      if (i!=j) f[i][j]=inf;
    for (int j=2;j<=n;j++)
     for (int i=j-1;i>=1;i--)
      for (int k=i;k<j;k++)
       f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+a[i]*a[k+1]*b[j]);  //方程不解释
    printf("%d\n",f[1][n]);
    return 0;
}