第三章动态规划

冷不防 2022-08-01 00:22 131阅读 0赞

**学习要点**

--------------------

理解动态规划的概念  
掌握动态规划算法的基本要素  
（1） 最优子结构性质  
（2） 重复子问题性质  
掌握设计动态规划算法的步骤  
（1） 找出最优解的性质，并刻画其结构特征  
（2） 递归地定义最优值  
（3） 以自底向上的方式计算最优解  
（4） 根据计算最优值时得到的信息构造最优解。

动态规划与分治法类似，都是将原问题划分成若干子问题求解，不同的是，适用于动态规划法解的问题，经分解得到的子问题往往不是互相独立的。并且，为了避免大量重复计算，可以用一个表来记录所有已解决的子问题的答案，不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划的基本思想。

--------------------

## 3.1 矩阵连乘问题 ##

矩阵连乘代码：

void matrixMultiply(int **a,int **b,int **c,int ra,int ca,int rb,int cb)
    {
        int i = 0;
        int j = 0;
        int k = 0;
    
        // 矩阵不可乘
        if (ca != rb)
            return;
    
        for (i = 0; i < ra; i++)
        {
            for (j = 0; j < cb; j++)
            {
                int sum = 0;
    
                for (k = 0; k < ca; k++)
                {
                    sum += a[i][k]*b[k][j];
                }
    
                c[i][j] = sum;
            }
        }
    }

给定 n 个矩阵 \{A1,A2,…,An\},其中 Ai 与 Ai+1 是可乘的，i = 1,2,3,…,n-1。考察这 n 个矩阵的连乘积 A1A2,…,An。

由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可依次次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可以递归的定义为：  
（1） 单个矩阵是完全加括号的  
（2） 矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积 B和 C的乘积并加括号，即 A = （BC）。

例如： 矩阵连乘积A1A2A3A4 可以有以下 5 种不同的完全加括号方式：  
(A1(A2(A3A4)))  
(A1((A2A3)A4))  
((A1A2)(A3A4))  
((A1(A2A3))A4)  
(((A1A2)A3)A4)

不同的加括号对应着不同的计算次序，不同的计算次序与计算量有密切的关系。  
从以下程序可以得出，矩阵的连乘的计算次数等于 ra\*ca\*cb。以3个矩阵为例：  
\{A1,A2,A3\} \{10\*100,100\*5,5\*50\}  
((A1A2)A3) 计算次数：10\*100\*5+10\*5\*50 = 5000+2500 = 7500  
(A1(A2A3)) 计算次数：100\*5\*50+10\*100\*50 = 25000+50000 = 75000  
可见运算次序是多么重要，于是我们需要寻找最优的运算次序使得乘次数最少。  
那么如何让矩阵的连乘次数最少呢？

m\[i\]\[j\] 数组

j  
i 　 1 2 3 4 5 6  
1 0 　 　 　 　 　  
2 　 0 　 　 　 　  
3 　 　 0 　 　 　  
4 　 　 　 0 　 　  
5 　 　 　 　 0 　  
6 　 　 　 　 　 0  
由于 i < j 因此求取问号区域的值

j  
i 　 1 2 3 4 5 6  
1 0 ? ? ? ? ?  
2 　 0 ? ? ? ?  
3 　 　 0 ? ? ?  
4 　 　 　 0 ? ?  
5 　 　 　 　 0 ?  
6 　 　 　 　 　 0  
m\[i\]\[j\] = min\{m\[i\]\[k\]+m\[k+1\]\[j\]+(pi-1\*pk\*pj)\} i < j,i <= k < j

j  
i 　 1 2 3 4 5 6  
1 0 k ? ? ? ?  
2 　 0 k ? ? ?  
3 　 　 0 ? ? ?  
4 　 　 　 0 ? ?  
5 　 　 　 　 0 ?  
6 　 　 　 　 　 0  
以 m\[1\]\[3\]为例，依次需要的数据有 m\[1\]\[1\],m\[2\]\[3\],m\[1\]\[2\],m\[3\]\[3\],看出来需要首先计算列以下内容，然后依次计算。

同理，求取 m\[1\]\[4\]，需要提前知道 m\[1\]\[1\],m\[2\]\[4\],m\[1\]\[2\],m\[3\]\[4\],m\[1\]\[3\],m\[4\]\[4\].

j  
i 　 1 2 3 4 5 6  
1 0 k k ? ? ?  
2 　 0 k k ? ?  
3 　 　 0 k ? ?  
4 　 　 　 0 ? ?  
5 　 　 　 　 0 ?  
6 　 　 　 　 　 0

由此得到循环的Code

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    void MatrixChain(int *p,int n,int **m,int **s);
    
    int main()
    {
        int i = 0;
        int n = 0;
        /*  矩阵维度的数组 N+1 */
        int *p = NULL;
        /*  矩阵最少乘法次数的数组 (N+1)*(N+1) */
        int **m = NULL;
        /*  矩阵拐弯的记录数组(N+1)*(N+1) */
        int **s = NULL;
    
        scanf("%d",&n);
    
        p = (int *)malloc((n+1)*sizeof(int));
        m = (int **)malloc((n+1)*sizeof(int*));
        s = (int **)malloc((n+1)*sizeof(int*));
    
        for (i = 0; i < n+1; i++)
        {
            *(m+i) = (int *)malloc((n+1)*sizeof(int));
            *(s+i) = (int *)malloc((n+1)*sizeof(int));
    
            scanf("%d",&(p[i]));
        }
    
        /*  计算矩阵相乘次数*/
        MatrixChain(p,n,m,s);
    
        free(p);
        free(m);
        free(s);
    
        return 0;
    }
    
    void MatrixChain(int *p,int n,int **m,int **s)
    {
        int i = 0;
        int j = 0;
        int k = 0;
    
        for (i = 0; i <= n; i++)
        {
            m[i][i] = 0;
        }
    
        for (j = 1; j <= n; j++)
        {
            for (i = j-1; i > 0; i--)
            {
                m[i][j] = m[i+1][j]+p[i-1]*p[i]*p[j];
                s[i][j] = i;
    
                for (k = i+1; k < j; k++)
                {
                    if (m[i][j] > m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j])
                    {
                        m[i][j] = m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                        s[i][j] = k;
                    }
                }
            }
        }
    
        printf("m[1][n] = %d",m[1][n]);
    }