算法入门-动态规划

算法
算法
发布日期:   2022-10-27
更新日期:   2022-11-08
文章字数:   6.2k
阅读时长:   26 分
阅读次数:  

动态规划

动态规划也是一种分治思想，但与分治算法不同的是，分治算法是把原问题分解为若干子问题，自顶向下求解各子问题，合并子问题的解，从而得到原问题的解。动态规划也是把原问题分解为若干子问题，然后自底向上，先求解最小的子问题，把结果存储在表格中，再求解大的子问题时，直接从表格中查询小的子问题的解，避免重复计算，从而提高算法效率。

与分治法的区别：在分治法中，各个子问题是互不相交的，即相互独立。如果各个子问题有重叠，不是相互独立的，动态规划闪亮登场！

算法要素：

什么问题可以使用动态规划呢？我们首先要分析问题是否具有以下两个性质：

  1. 最优子结构

    **最优子结构性质是指问题的最优解包含其子问题的最优解。**最优子结构是使用动态规划的最基本条件，如果不具有最优子结构性质，就不可以使用动态规划解决。

  2. 子问题重叠

    子问题重叠是指在求解子问题的过程中，有大量的子问题是重复的，那么只需要求解一次，然后把结果存储在表中，以后使用时可以直接查询，不需要再次求解。

    子问题重叠不是使用动态规划的必要条件，但问题存在子问题重叠更能够充分彰显动态规划的优势。

解题秘籍：

遇到一个实际问题，如何采用动态规划来解决呢？

  1. 分析最优解的结构特征。
  2. 建立最优值的递归式。
  3. 自底向上计算最优值，并记录。
  4. 构造最优解。

最长公共子序列

问题分析：

给定两个序列 X={x1，x2，x3，…，x m}和 Y={y1，y2，y3，…，yn}，找出 X 和 Y 的一个最长的公共子序列。

例如：X=（A，B，C，B，A，D，B），Y=（B，C，B，A，A，C），那么最长公共子序列是 B，C，B，A。

如何找到最长公共子序列呢？

如果使用暴力搜索方法，需要穷举 X 的所有子序列，检查每个子序列是否也是 Y 的子序列，记录找到的最长公共子序列。X 的子序列有 2m 个，因此暴力求解的方法时间复杂度为指数阶，这是我们避之不及的爆炸性时间复杂度。

那么能不能用动态规划算法呢？
下面分析该问题是否具有最优子结构性质。

  1. 分析最优解的结构特征

    假设已经知道 Zk={z1，z2，z3，…，zk}是 X m={x1，x2，x3，…，x m}和 Yn={y1，y2，y3，…，y n}的最长公共子序列。

    这个假设很重要，我们都是这样假设已经知道了最优解。

    那么可以分 3 种情况讨论。

    • xm= yn= zk：那么 Zk−1={z1，z2，z3，…，zk−1}是 Xm−1 和 Yn−1 的最长公共子序列：

      image-20221027222127785

      反证法证明：如果 Zk−1 ={z1，z2，z3，…，zk−1 }不是 X m−1 和 Yn−1 的最长公共子序列，那么它们一定存在一个最长公共子序列。设 M 为 X m−1 和 Yn−1 的最长公共子序列，M 的长度大于Zk−1 的长度，即|M|>|Zk−1|。如果在 X m−1 和 Yn−1 的后面添加一个相同的字符 xm= y n，则 zk=xm=y n，|M+{zk}|>|Zk−1+{zk}|=|Zk|，那么 Zk 不是 X m 和 Yn 的最长公共子序列，这与假设 Zk 是 X m 和 Yn 的最长公共子序列矛盾，问题得证。

    • xm≠yn，xm≠zk：我们可以把 xm 去掉，那么 Zk 是 Xm−1 和 Yn 的最长公共子序列：

      image-20221027222217619

      反证法证明：如果 Zk 不是 X m−1 和 Y n 的最长公共子序列，那么它们一定存在一个最长公共子序列。设 M 为 X m−1 和 Y n 的最长公共子序列，M 的长度大于 Zk 的长度，即|M|>|Zk|。如果我们在 X m−1 的后面添加一个字符 x m，那么 M 也是 X m 和 Yn 的最长公共子序列，因为|M|>|Zk|，那么 Zk 不是 X m 和 Y n 的最长公共子序列，这与假设 Zk 是 X m 和 Y n 的最长公共子序列矛盾，问题得证。

    • xm≠yn，yn≠zk：我们可以把 y n 去掉，那么 Zk 是 X m 和 Yn−1 的最长公共子序列：

      image-20221027222826143

      反证法证明：如果 Zk 不是 X m 和 Y n−1 的最长公共子序列，那么它们一定存在一个最长公共子序列。设 M 为 X m 和 Y n−1 的最长公共子序列，M 的长度大于 Zk 的长度，即|M|>|Zk|。如果我们在 Yn−1 的后面添加一个字符 yn，那么 M 也是 Xm 和 Yn 的最长公共子序列，因为|M|>|Zk|，那么 Zk不是 Xm 和 Yn 的最长公共子序列，这与假设 Zk 是 Xm 和 Yn 的最长公共子序列矛盾，问题得证。

  2. 建立最优值的递归式

    设 c[i][j]表示 X i 和 Y j 的最长公共子序列长度。

    • xm = yn = zk：那么 c[i][j] = c[i−1][j−1]+1；

    • xm ≠ yn：那么我们只需要求解 X i 和 Y j−1 的最长公共子序列和 X i−1 和 Y j 的最长公共子序列，比较它们的长度哪一个更大，就取哪一个值。即 c[i][j]= max{c[i][j−1],c[i−1][j]}。

    • 最长公共子序列长度递归式：

      image-20221027223715163

  3. 底向上计算最优值，并记录最优值和最优策略

    i=1 时：{x1 }和{y1，y2，y3，…，y n}中的字符一一比较，按递归式求解并记录最长公共子序列长度。

    i=2 时：{x2 }和{y1，y2，y3，…，y n}中的字符一一比较，按递归式求解并记录最长公共子序列长度。

    …

    i=m 时：{x m}和{y1，y2，y3，…，yn}中的字符一一比较，按递归式求解并记录最长公共子序列长度。

  4. 构造最优解

    上面的求解过程只是得到了最长公共子序列长度，并不知道最长公共子序列是什么，那怎么办呢？

    例如，现在已经求出 c[m][n]=5，表示 X m 和 Y n 的最长公共子序列长度是 5，那么这个 5是怎么得到的呢？我们可以反向追踪 5 是从哪里来的。根据递推式，有如下情况。

    x i = y j 时：c[i][j]= c[i−1][j−1]+1；

    x i ≠ y j 时：c[i][j]= max{c[i][j−1], c[i−1][j]}；

    那么 c[i][j]的来源一共有 3 个：c[i][j]= c[i−1][j−1]+1，c[i][j]= c[i][j−1]，c[i][j]= c[i−1][j]。在第 3 步自底向上计算最优值时，用一个辅助数组 b [i][j]记录这 3 个来源：

    c[i][j]= c[i−1][j−1]+1，b[i][j]=1；

    c[i][j]= c[i][j−1]，b[i][j]=2；

    c[i][j]= c[i−1][j]，b[i][j]=3。

    这样就可以根据 b[m][n]反向追踪最长公共子序列，当 b[i][j]=1 时，输出 x i；当 b [i][j]=2时，追踪 c[i][j−1]；当 b[i][j]=3 时，追踪 c[i−1][j]，直到 i=0 或 j=0 停止。

图解分析：

以字符串 s1 =“ABCADAB”，s2=“BACDBA”为例。

  1. 初始化

    len1=7，len2=6，初始化 c[][]第一行、第一列元素为 0：

    image-20221027225817829

  2. i=1：s1[0]与 s2[j−1]比较，j=1，2，3，…，len2。即“A”与“BACDBA”分别比较一次。

    如果字符相等，c[i][j]取左上角数值加 1，记录最优值来源 b[i][j]=1。

    如果字符不等，取左侧和上面数值中的最大值。如果左侧和上面数值相等，默认取左侧数值。如果 c[i][j]的值来源于左侧 b[i][j]=2，来源于上面 b[i][j]=3。

    • j=1：A≠B，左侧=上面，取左侧数值，c[1][1]= 0，最优策略来源 b[1][1]=2：

      image-20221027230443409

    • j=2：A=A，则取左上角数值加 1，c[1][2]= c[0][1]+1=2，最优策略来源 b[1][2] =1：

      image-20221027230615500

    • j=3：A≠C，左侧≥上面，取左侧数值，c[1][3]= 1，最优策略来源 b[1][3] =2：

      image-20221027230649108

    • j=6：A=A，则取左上角数值加 1，c[1][6]=1，最优策略来源 b[1][6]=1：

      image-20221027230840156

  3. i=2：s1[1]与 s2 [j−1]比较，j=1，2，3，…，len2。即“B”与“BACDBA”分别比较一次。

    如果字符相等，c[i][j]取左上角数值加 1，记录最优值来源 b[i][j]=1。

    如果字符不等，取左侧和上面数值中的最大值。如果左侧和上面数值相等，默认取左侧数值。如果 c[i][j]的值来源于左侧 b[i][j]=2，来源于上面 b[i][j]=3：

    image-20221027231109658

  4. 继续处理 i=2，3，…，len1：s1[i−1]与 s2 [j−1]比较，j=1，2，3，…，len2。处理结果如下：

    image-20221027231613378

    c[][]右下角的值即为最长公共子序列的长度。

    c[7][6]=4，即字符串 s1 =“ABCADAB”，s2 =“BACDBA”的最长公共子序列的长度为 4。

    那么最长公共子序列包含哪些字符呢？

  5. 构造最优解

    首先读取 b[7][6]=2，说明来源为 2，向左找 b[7][5]；

    b[7][5]=1，向左上角找 b[6][4]，返回时输出 s[6]=“B”；
    b[6][4]=3，向上找 b[5][4]；
    b[5][4]=1，向左上角找 b[4][3]，返回时输出 s[4]=“D”；
    b[4][3]=2，向左找 b[4][2]；
    b[4][2]=1，向左上角找 b[3][1]，返回时输出 s[3]=“C”；
    b[3][1]=3，向上找 b[2][1]；
    b[2][1]=1，向左上角找，返回时输出 s[1]=“B”；

    b[1][0]中列为 0，算法停止，返回，输出最长公共子序列为 BCDB：

    image-20221027232645959

    即输出追踪到的左上角元素

代码实现：

  1. 最长公共子序列求解函数

    首先计算两个字符串的长度，然后从 i=1 开始，s1 [0]与 s2 中的每一个字符比较。
    如果当前字符相同，则公共子序列的长度为 c[i−1][j−1]+1，并记录最优策略来源 b[i][j] = 1。
    如果当前字符不相同，则公共子序列的长度为 c[i][j−1]和 c[i−1][j]中的最大值，如果c[i][j−1]≥c[i−1][j]，则最优策略来源 b[i][j]=2；如果 c[i][j−1]<c[i−1][j]，则最优策略来源b[i][j]=3。直到 i> len1 时，算法结束，这时 c[len1][len2]就是我们要的最长公共序列长度。

    void LCSL()
{
    int i,j;
    for(i = 1;i <= len1;i++)//控制s1序列不同的子问题
      for(j = 1;j <= len2;j++)//控制s2序列不同的子问题
      {
        if(s1[i-1]==s2[j-1])
        {
            c[i][j] = c[i-1][j-1]+1;//如果当前字符相同，则公共子序列的长度为该字符前的最长公共序列+1
            b[i][j] = 1;
        }
        else
        {
             if(c[i][j-1]>=c[i-1][j])
            {
                c[i][j] = c[i][j-1];
                b[i][j] = 2;
            }
            else
            {
                c[i][j] = c[i-1][j];
                b[i][j] = 3;
            }
        }
     }
}

  2. 最优解输出函数

    输出最优解仍然使用倒推法。因为我们在求最长公共子序列长度 c[i][j]的过程中，用 b[i][j]记录了 c[i][j]的来源，那么就可以根据 b[i][j]数组倒推最优解。

    如果 b[i][j]=1，说明 s1[i−1]=s2[j−1]，那么我们就可以递归输出 print(i−1，j−1)；然后输出 s1[i−1]。

    如果 b[i][j]=2，说明 s1[i−1]≠s2[j−1]且最优解来源于 c[i][j]=c[i][j−1]，递归输出 print(i，j−1)。

    如果 b[i][j]=3，说明 s1[i−1]≠s2[j−1]且最优解来源于 c[i][j]=c[i−1][j]，递归输出 print(i−1，j)。
    当 i==0||j==0 时，递归结束。

    void print(int i, int j)//根据记录下来的信息构造最长公共子序列（从b[i][j]开始递推）
{
    if(i==0 || j==0) return;
    if(b[i][j]==1)
    {
        print(i-1,j-1);
        cout<<s1[i-1];
    }
    else if(b[i][j]==2)
            print(i,j-1);
         else
            print(i-1,j);
}

完整代码：

//program 4-1
#include <iostream>
#include<cstring>
using namespace std;
const int N=1002;
int c[N][N],b[N][N];
char s1[N],s2[N];
int len1,len2;

void LCSL()
{
    int i,j;
    for(i = 1;i <= len1;i++)//控制s1序列不同的子问题
      for(j = 1;j <= len2;j++)//控制s2序列不同的子问题
      {
        if(s1[i-1]==s2[j-1])
        {
            c[i][j] = c[i-1][j-1]+1;//如果当前字符相同，则公共子序列的长度为该字符前的最长公共序列+1
            b[i][j] = 1;
        }
        else
        {
             if(c[i][j-1]>=c[i-1][j])
            {
                c[i][j] = c[i][j-1];
                b[i][j] = 2;
            }
            else
            {
                c[i][j] = c[i-1][j];
                b[i][j] = 3;
            }
        }
     }
}

void print(int i, int j)//根据记录下来的信息构造最长公共子序列（从b[i][j]开始递推）
{
    if(i==0 || j==0) return;
    if(b[i][j]==1)
    {
        print(i-1,j-1);
        cout<<s1[i-1];
    }
    else if(b[i][j]==2)
            print(i,j-1);
         else
            print(i-1,j);
}

int main()
{
    int i,j;
    cout << "输入字符串s1:"<<endl;
    cin >> s1;
    cout << "输入字符串s2:"<<endl;
    cin >> s2;
    len1 = strlen(s1);//计算两个字符串的长度
    len2 = strlen(s2);
    for(i = 0;i <= len1;i++)
    {
        c[i][0]=0;//初始化第一列为0
    }
    for(j = 0;j<= len2;j++)
    {
        c[0][j]=0;//初始化第一行为0
    }
    LCSL();
    cout << "s1和s2的最长公共子序列长度是:"<<c[len1][len2]<<endl;
    cout << "s1和s2的最长公共子序列是:";
    print(len1,len2);
    cout<<endl;
    // /*用于测试
    cout<<"c[i][j]数组："<<endl;
    for(i = 0;i <= len1;i++)
    {
        for(j = 0;j <= len2;j++)
          cout <<"  "<<c[i][j];
        cout<<endl;
    }
    cout<<"b[i][j]数组："<<endl;
    for(i = 0;i <= len1;i++)
    {
        for(j = 0;j <= len2;j++)
          cout <<"  "<<b[i][j];
        cout<<endl;
    }
    // */用于测试
    return 0;
}

算法复杂度：

  1. 时间复杂度：

    由于每个数组单元的计算耗费 Ο(1)时间，如果两个字符串的长度分别是 m、n，那么算法时间复杂度为 Ο(m*n)。

  2. 空间复杂度：

    空间复杂度主要为两个二维数组 c[][]，b[][]，占用的空间为 O(m*n)。

优化拓展：

因为 c[i][j]有 3 种来源：c[i−1][j−1]+1、c[i][j−1]、c[i−1][j]。我们可以利用 c 数组本身来判断来源于哪个值，从而不用 b[][]，这样可以节省 O(mn)个空间。但因为 c 数组还是 O(mn)个空间，所有空间复杂度数量级仍然是 O(m*n)，只是从常数因子上的改进。

image-20221028175628346

矩阵连乘

问题分析：

矩阵连乘问题就是对于给定 n 个连乘的矩阵，找出一种加括号的方法，使得矩阵连乘的计算量（乘法次数）最小。

  1. 什么是矩阵可乘？

    如果两个矩阵，第 1 个矩阵的列等于第 2 个矩阵的行时，那么这两个矩阵是可乘的。

    image-20221028180740102

  2. 矩阵相乘后的结果是什么？

    **多个矩阵相乘的结果矩阵，其行、列分别等于第 1 个矩阵的行、最后 1 个矩阵的列。**而且无论矩阵的计算次序如何都不影响它们的结果矩阵。

  3. 两个矩阵相乘需要多少次乘法？

    Am×n、An×k 相乘执行乘法运算的次数为 m×n×k。

如果穷举所有的加括号方法，那么加括号的所有方案是一个卡特兰数序列，其算法时间复杂度为 2n，是指数阶。因此穷举的办法是很糟的，那么能不能用动态规划呢？

下面分析矩阵连乘问题 AiAi+1…Aj 是否具有最优子结构性质。

  1. 分析最优解的结构特征

    • 假设我们已经知道了在第 k 个位置加括号会得到最优解，那么原问题就变成了两个子问题：（AiAi+1…Ak），（Ak+1Ak+2…Aj）:

      image-20221028181917124

      原问题的最优解是否包含子问题的最优解呢？

    • 假设 AiAi+1…Aj 的乘法次数是 c，（AiAi+1…Ak）的乘法次数是 a，（Ak+1Ak+2…Aj）的乘法次数是 b，（AiAi+1…Ak）和（Ak+1Ak+2…Aj）的结果矩阵相乘的乘法次数是 d，那么c=a+b+d，无论两个子问题（AiAi+1…Ak）、（Ak+1Ak+2…Aj）的计算次序如何，都不影响它们结果矩阵，两个结果矩阵相乘的乘法次数 d 不变。

      因此我们只需要证明如果 c 是最优的，则 a 和 b 一定是最优的（即原问题的最优解包含子问题的最优解）。

  2. 建立最优值递归式

    • 用 m[i][j]表示 AiAi+1 …Aj 矩阵连乘的最优值，那么两个子问题（AiAi+1 …Ak ）、（Ak+1Ak+2…Aj）对应的最优值分别是 m[i][k]、m[k+1][j]。剩下的只需要考查（AiAi+1…Ak）和（Ak+1Ak+2…Aj）的结果矩阵相乘的乘法次数了。

    • 设矩阵 Am 的行数为 p m，列数为 q m，m=i，i+1, …，j，且矩阵是可乘的，即相邻矩阵前一个矩阵的列等于下一个矩阵的行（q m= p m+1）。（AiAi+1…Ak）的结果是一个 p i×q k矩阵，（Ak+1Ak+2…Aj）的结果是一个 p k+1×qj 矩阵，q k= p k+1，两个结果矩阵相乘的乘法次数是 p i*p k+1 *q j。

    • 当 i=j 时，只有一个矩阵，m[i][j]=0；

      当 i>j 时，m[i][j]=min{m[i][k]+m[k+1][j]+pi×pk+1×qj}

      如果用一维数组 p[]来记录矩阵的行和列，第 i 个矩阵的行数存储在数组的第 i−1 位置，列数存储在数组的第 i 位置，那么 pip k+1qj 对应的数组元素相乘为 p[i−1]p[k] p[j]，原递归式变为：

      image-20221028183443792

  3. 自底向上计算并记录最优值

    先求两个矩阵相乘的最优值，再求 3 个矩阵相乘的最优值，直到 n 个矩阵连乘的最优值。

  4. 构造最优解

    上面得到的最优值只是矩阵连乘的最小的乘法次数，并不知道加括号的次序，需要从记录表中还原加括号次序，构造出最优解，例如 A1（A2A3）。

图解分析：

假设有5个矩阵：

image-20221028184059795

  1. 初始化

    采用一维数组 p[]记录矩阵的行和列，实际上只需要记录每个矩阵的行，再加上最后一个矩阵的列即可。m[i][i]=0，s[i][i]=0，其中 i= 1，2，3，4，5。

    image-20221028184442920

    最优值数组 m[i][i]=0，最优决策数组 s[i][i]=0，其中 i= 1，2，3，4，5。

    image-20221028184457563

  2. 计算两个矩阵相乘的最优值

    规模 r=2。根据递归式：

    image-20221028185814891

    • A1 *A2：k=1，m[1][2]=min{ m[1][1]+ m[2][2]+p0p1p2 }=150；s[1][2]=1。

    • A2 *A3：k=2，m[2][3]=min{ m[2][2]+ m[3][3]+p1p2p3 }=400；s[2][3]=2。

    • A3 *A4：k=3，m[3][4]=min{ m[3][3]+ m[4][4]+p2p3p4 }=160；s[3][4]=3。

    • A4 *A5：k=4，m[4][5]=min{ m[4][4]+ m[5][5]+p3p4p5 }=64； s[4][5]=4。

      image-20221028185848792

  3. 计算 3 个矩阵相乘的最优值

    规模 r=3。根据递归式：

    image-20221028185814891

    image-20221028190045501

    image-20221028190053112

    image-20221028190209778

  4. 计算 4 个矩阵相乘的最优值

    image-20221028190253904

  5. 计算 5 个矩阵相乘的最优值

    image-20221028190650549

    image-20221028190705171

  6. 根据最优解

    根据最优决策数组 s[][]中的数据来构造最优解，即加括号的位置。

    首先读取 s[1][5]=4，表示在 k=4 的位置把矩阵分为两个子问题：（A1A2A3A4）、A5。

    再看第一个子问题（A1A2A3A4），读取 s[1][4]=1，表示在 k=1 的位置把矩阵分为两个子问题：A1、（A2A3A4）。

    子问题 A1 不用再分解，输出；子问题（A2A3A4），读取 s[2][4]=2，表示在 k=2 的位置把矩阵分为两个子问题：A2、（A3A4）。

    子问题 A2 不用再分解，输出；子问题(A3A4 )，读取 s[3][4]=3，表示在 k=3 的位置把矩阵分为两个子问题：A3、A4。这两个子问题都不用再分解，输出

    子问题 A5 不用再分解，输出。

    image-20221028190934126

    最优解为：（（A1（A2（A3A4）））A5）。
    最优值为：314。

代码实现：

按照算法思想和设计，以下程序将矩阵的行和列存储在一维数组 p[]，m[][]数组用于存储分成的各个子问题的最优值，s[][]数组用于存储各个子问题的决策点，然后在一个 for 循环里，将问题分为规模为 r 的子问题，求每个规模子问题的最优解，那么得到的 m[1][n]就是最小的计算量。

  1. 矩阵连乘求解函数

    首先将数组 m[][]，s[][]初始化为 0，然后自底向上处理不同规模的子问题，r 为问题的规模，r= 2；r <= n；r++，当 r= 2 时，表示矩阵连乘的规模为 2，即两个矩阵连乘。求解两个矩阵连乘的最优值和最优策略，根据递归式对每一个 k 值，找到最小值用 m[i][j]记录，并用 s[i][j]记录取得最小值的 k 值。

    void matrixchain()
{
    int i,j,r,k;
    memset(m,0,sizeof(m));
    memset(s,0,sizeof(s));
    for(r = 2; r <= n; r++)         //不同规模的子问题
    {
        for(i = 1; i <= n-r+1; i++)
        {
           j = i + r - 1;
           m[i][j] = m[i+1][j] + p[i-1] * p[i] * p[j];  //决策为k=i的乘法次数
           s[i][j] = i;                     //子问题的最优策略是i;
           for(k = i+1; k < j; k++) //对从i到j的所有决策，求最优值，记录最优策略
            {
                int t = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j];
                if(t < m[i][j])
                {
                    m[i][j] = t;
                    s[i][j] = k;
                }
            }
        }
    }
}

  2. 最优解输出函数

    根据存储表格 s[][]中的数据来构造最优解，即加括号的位置。首先打印一个左括号，然后递归求解子问题 print（i，s[i][j]），print（s[i][j]+1，j），再打印右括号，当 i=j 即只剩下一个矩阵时输出该矩阵即可。

    void print(int i,int j)
{
    if( i == j )
    {
       cout <<"A[" << i << "]";
       return ;
    }
    cout << "(";
    print(i,s[i][j]);
    print(s[i][j]+1,j);
    cout << ")";
}

完整代码：

//program 4-4
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int msize = 100;
int p[msize];
int m[msize][msize];
int s[msize][msize];
int n;

void matrixchain()
{
    int i,j,r,k;
    memset(m,0,sizeof(m));
    memset(s,0,sizeof(s));
    for(r = 2; r <= n; r++)         //不同规模的子问题
    {
        for(i = 1; i <= n-r+1; i++)
        {
           j = i + r - 1;
           m[i][j] = m[i+1][j] + p[i-1] * p[i] * p[j];  //决策为k=i的乘法次数
           s[i][j] = i;                     //子问题的最优策略是i;
           for(k = i+1; k < j; k++) //对从i到j的所有决策，求最优值，记录最优策略
            {
                int t = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j];
                if(t < m[i][j])
                {
                    m[i][j] = t;
                    s[i][j] = k;
                }
            }
        }
    }
}
void print(int i,int j)
{
    if( i == j )
    {
       cout <<"A[" << i << "]";
       return ;
    }
    cout << "(";
    print(i,s[i][j]);
    print(s[i][j]+1,j);
    cout << ")";
}
int main()
{
    cout << "请输入矩阵的个数 n:";
    cin >> n;
    int i ,j;
    cout << "请依次输入每个矩阵的行数和最后一个矩阵的列数:";
    for (i = 0; i <= n; i++ )
        cin >> p[i];
    matrixchain();
    print(1,n);
    cout << endl;
    /*用于测试
    for (i = 1; i <= n; i++ )
        {
          for (j = i; j <= n; j++ )
            cout << m[i][j]<<"  " ;
          cout << endl;
        }
     for (i = 1; i <= n; i++ )
        {
          for (j = i; j <= n; j++ )
            cout << s[i][j]<<"  " ;
          cout << endl;
        }
    cout << endl;
    */
    cout << "最小计算量的值为 " << m[1][n] << endl;
}

算法复杂度：

  1. 时间复杂度

    由程序可以得出：语句 t= m[i][k] + m[k+1][j] +p[i−1]*p[k]*p[j]，它是算法的基本语句，在 3 层 for 循环中嵌套。最坏情况下，该语句的执行次数为 O(n3)，print()函数算法的时间主要取决于递归，时间复杂度为 O(n)。故该程序的时间复杂度为 O(n3)。

  2. 空间复杂度

    该程序的输入数据的数组为 p[]，辅助变量为 i、j、r、t、k、m[][]、s[][]，空间复杂度取决于辅助空间，因此空间复杂度为 O(n2)。

文章作者: QT-7274
文章链接: https://qt-7274.github.io/2022/10/27/suan-fa-ru-men-dong-tai-gui-hua/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 QT-7274 !
算法
赏
评论
  目录