矩阵连乘—详细讲解

原文来自我的CSDN博客

初次接触dp，就看到很多位大佬给出自己的见解，dp算是最难的算法之一吧，主要在于灵活度高，需要自己推出动态规划方程

1. 100个动态规划方程传送门

2. 涉及到dp问题那么for循环一般从1开始遍历，这样会好些，虽然目前的我还没理解，但是看到许多大佬写代码都是从1开始遍历，那我也慢慢的改变。

   下面我就几个问题来说明一下矩阵连乘问题

   矩阵连乘问题-求最优值

   题目描述
   使用动态规划算法求解矩阵连乘问题，输出最少乘法次数。
   输入
   每组数据包括两行，第一行为数组长度n，第二行为存储矩阵维数的一维数组。
   输出
   矩阵连乘最优计算次数。
   样例输入
   7
   30 35 15 5 10 20 25
   样例输出
   15125

ps:

刚刚开始拿到这个题目的时候，我很懵逼，看不懂题目的意思，所以我就查资料，之后才明白题目的意思，题目给的输入，其实是一个数组，用来存储矩阵的行和列，输出要输出最少乘法运算

通过这个表格我们可以直观地了解题目意思，以及得到许多有用的信息

1. 矩阵的个数等于数组长度减一
2. p[0],p[1]代表第一个矩阵的行数和列数，p[1],p[2]代表第二个矩阵的行数和列数......p[5],p[6]代表第六个矩阵的行数和列数

写代码之前我们要得到状态转移方程方程

dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]a[k]a[j]);

我们用三层循环i,j,k分别枚举连乘长度，连乘左边界和划分点

最后这张图片里面应该保存每次长度的最小值，我们先求出长度为2的有多少种情况，然后把最小的填入表格，再依次求3 4 ....6;后面一步都要依赖于前面计算的最小值
代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int a[maxn], dp[maxn][maxn];
int main()
{
    int n;
    while (~scanf("%d", &n))
    {
        for (int i = 0; i < n; ++i) //从零开始的遍历
            scanf("%d", &a[i]);
        memset(dp, 0, sizeof(dp));               //首先把整个数组初始化
        for (int r = 2; r < n; ++r)              //枚举连乘长度
        {                                        //因为长度为1的矩阵不足以相乘，所以都为0
            for (int i = 1; i < n - r + 1; ++i) //枚举连乘左边界
            {
                int j = i + r - 1;  //枚举连乘又边界
                dp[i][j] = dp[i + 1][j] + a[i - 1] * a[i] * a[j];
                //其实它是 dp[i][j] =dp[i][i](等于0)+ dp[i + 1][j] + a[i - 1] * a[i] * a[j];
                for (int k = i + 1; k < j; ++k)
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + a[i - 1] * a[k] * a[j]); //从不同位置断开取最小值
            }
        }
        printf("%d\n", dp[1][n - 1]); //最后只要找到右上角的数字就是所有矩阵相乘的最小值
    }
    return 0;
}

大佬一般是从1开始遍历，思路都是一样的，就是一些地方需要改动一下

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int a[maxn], dp[maxn][maxn];
int main()
{
   int n;
   while (~scanf("%d", &n))
   {
      for (int i = 1; i <= n; ++i)
         scanf("%d", &a[i]);
      memset(dp, 0, sizeof(dp));
      for (int r = 2; r < n; ++r)
      {
         for (int i = 1; i < n - r + 1; ++i)
         {
            int j = i + r - 1;
            dp[i][j] = dp[i + 1][j] + a[i] * a[i + 1] * a[j + 1];
            for (int k = i + 1; k < j; ++k)
               dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + a[i] * a[k + 1] * a[j + 1]);
         }
      }
      printf("%d\n", dp[1][n - 1]);
   }
   return 0;
}

简洁明了的代码

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1e3 + 5;
int a[maxn], dp[maxn][maxn];
int main()
{
    int n;
    while (~scanf("%d", &n))
    {
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        for (int l = 2; l < n; ++l)
        { //枚举连乘长度
            for (int i = 1; i + l <= n; ++i)
            {                  //枚举连乘左边界
                int j = i + l; //连乘右边界
                dp[i][j] = inf;
                for (int k = i + 1; k < j; ++k)
                { //枚举划分点
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]);
                }
            }
        }
        printf("%d\n", dp[1][n]);
    }
    return 0;
}

矩阵连乘问题-构造最优解

题目描述
使用动态规划算法求解矩阵连乘问题。
输入
每组数据包括两行，第一行为数组长度n，第二行为存储矩阵维数的一维数组。
输出
矩阵连乘最优计算次序。
样例输入

7
30 35 15 5 10 20 25

样例输出

A[2:2] * A[3:3]
A[1:1] * A[2:3]
A[4:4] * A[5:5]
A[4:5] * A[6:6]
A[1:3] * A[4:6]

多用一个数组储存每一个区间的最优划分点，递归输出

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
const int inf = 0x3f3f3f3f;
int a[maxn], dp[maxn][maxn], s[maxn][maxn];
void solve(int l, int r)
{
    if (s[l][r]) //查表递归输出
    {
        solve(l, s[l][r]);
        solve(s[l][r], r);
        printf("A[%d:%d] * A[%d:%d]\n", l, s[l][r] - 1, s[l][r], r - 1);
    }
}
int main()
{
    int n;
    while (~scanf("%d", &n))
    {
        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        memset(dp, 0, sizeof(dp));
        for (int l = 2; l < n; ++l)
        {
            for (int i = 1; i + l <= n; ++i)
            {
                int j = i + l;
                dp[i][j] = inf;
                for (int k = i + 1; k < j; ++k)
                {
                    int x = dp[i][k] + dp[k][j] + a[i] * a[k] * a[j];
                    if (dp[i][j] > x)
                    {
                        dp[i][j] = x;
                        s[i][j] = k; //记录最优划分点
                    }
                }
            }
        }
        solve(1, n); //递归输出
    }
    return 0;
}

感觉这个构造法还没理解透，下次理解了再来更新~

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
const int inf = 0x3f3f3f3f;
int a[maxn], dp[maxn][maxn], s[maxn][maxn];
void solve(int l, int r)
{
    if (s[l][r]) //查表递归输出
    {
        solve(l, s[l][r]);
        solve(s[l][r]+1, r);
        printf("A[%d:%d] * A[%d:%d]\n", l, s[l][r], s[l][r]+1, r);
    }
}
int main()
{
    int n;
    while (~scanf("%d", &n))
    {
        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        memset(dp, 0, sizeof(dp));
        for (int l = 2; l < n; ++l)
        {
            for (int i = 1; i + l <= n; ++i)
            {
                int j = i + l-1;
                dp[i][j] = dp[i + 1][j] + a[i] * a[i + 1] * a[j + 1];
                s[i][j] = i;
                for (int k = i + 1; k < j; ++k)
                {
                    int x = dp[i][k] + dp[k + 1][j] + a[i] * a[k + 1] * a[j + 1];
                    if (dp[i][j] > x)
                    {
                        dp[i][j] = x;
                        s[i][j] = k; //记录最优划分点打表
                    }
                }
            }
        }
        solve(1, n-1); //递归输出
    }
    return 0;
}