算法笔记 - 矩阵连乘问题动态规划

阳光穿透心脏的1/2处 2022-12-30 13:37 167阅读 0赞

###  算法笔记 - 矩阵连乘问题 动态规划 ###

#### Intro ####

*  下午课上提到了矩阵连乘，这是个经典的动态规划问题，复习一下。
 *  主要就是自底向上的思路，枚举每个区间，子问题的最优解最后得到整体最优解（注意枚举的常见写法）。
 *  状态转移方程：

m ( i , j ) = \{ 0 i = j m i n i ≤ k < j \{ m ( i , k ) + m ( k + 1 , j ) + a i ( x ) ∗ a k ( y ) ∗ a j ( y ) \} i < j m(i, j)=\\begin\{cases\} & 0 & i=j \\\\ & min\_\{i \\leq k < j\} \\\{ m(i, k) + m(k+1, j) + a\_i(x) \* a\_k(y) \* a\_j(y) \\\} & i < j \\end\{cases\} m(i,j)=\{ 0mini≤k<j\{ m(i,k)\+m(k\+1,j)\+ai(x)∗ak(y)∗aj(y)\}i=ji<j

#### Code ####

*  [EOJ 1051][]

//
    // Created by jiangnanmax on 2020/12/25.
    // @email jiangnanmax@gmail.com
    //
    
    #include <iostream>
    #include <cstring>
    #include <cmath>
    
    using namespace std;
    
    typedef long long int ll;
    const int INF = 0x3f3f3f3f;
    
    struct Matrix { 
        int x;
        int y;
    };
    
    Matrix matrix[50];
    ll dp[50][50];
    
    int main() { 
        int N;
        cin>>N;
        while (N--) { 
            int n;
            cin>>n;
            for (int i = 0; i < n; i++) { 
                cin>>matrix[i].x>>matrix[i].y;
            }
            memset(dp, INF, sizeof(dp));
            for (int i = 0; i < n; i++) { 
                dp[i][i] = 0;
            }
            for (int len = 1; len < n; len++) { 
                for (int i = 0; i + len < n ; i++) { 
                    int j = i + len;
                    for (int k = i; k < j; k++) { 
                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + matrix[i].x * matrix[k].y * matrix[j].y);
                    }
                }
            }
            cout<<dp[0][n-1]<<endl;
        }
        return 0;
    }

[EOJ 1051]: https://acm.ecnu.edu.cn/problem/1051/