9.4 Matrix multiplication

矩阵链相乘，求最小的乘法次数

Given a sequence of matrices, we want to find the most efficient way to multiply these matrices together. The problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications.
We have many options because matrix multiplication is associative. In other words, no matter how we parenthesize the product, the result will be the same. For example, if we had four matrices A, B, C, and D, we would have:
(ABC)D = (AB)(CD) = A(BCD) = A(BC)D = ....

However, the order in which we parenthesize the product affects the number of simple arithmetic operations needed to compute the product, or the efficiency. For example, suppose A is a 10 × 30 matrix, B is a 30 × 5 matrix, and C is a 5 × 60 matrix. Then,
(AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations
A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations.

Clearly the first method is the more efficient. Now that we have identified the problem, how do we determine the optimal parenthesization of a product of n matrices? We could go through each possible parenthesization (brute force), but this would require time exponential in the number of matrices, which is very slow and impractical for large n. The solution, as we will see, is to break up the problem into a set of related subproblems. By solving subproblems one time and reusing these solutions many times, we can drastically reduce the time required. This is known as dynamic programming.

先形式化一下我们的input，矩阵链{A1，A2，...，An}，其中对于矩阵Ai，它是一个Pi-1 * Pi的矩阵。m[i,j] 表示{Ai,Ai+1,..., Aj}相乘的最小的乘法次数

这个递归的思路其实和第一个问题有点类似，先看怎么递归。

首先我们要找出一个点来分隔这个链，相当于这个点把这个问题转换为了 该点前一部分的矩阵链的最小的乘法次数问题和该点后一部分的矩阵链的最小的乘法次数问题。

但是这个点怎么找呢？和第一个例子一样，我们直接遍历的来找。

所以我们的递归应该是这样的：
m[i,j] = mini<=k<=j (m[i,k] + m[k+1,j] + Pi-1PkPj)

当然，这是对于i!=j的情况，当i==j的时候呢？显然 是0了，因为我们的矩阵链就一个矩阵。

EXAMPLE INPUT

9 6 10 11 8 4 5 7 12 13

EXAMPLE OUTPUT

2816

主程序 (不能修改)

#include "source.c"
#include <stdio.h>

int main() {
    int dimensions[10];
    for (int i = 0; i < 10; ++ i) {
        scanf("%d", &dimensions[i]);
    }
    printf("%d", getMultiplications(9, dimensions));
}

我的答案

int dp[10][10];//从i到j相乘所需要的最少计算次数 
int memeo[10][10];//储存从i到j在哪里截断 
int getMultiplications(int n,int *dimensions){
    int i,j,k,l,tmp;
    for (i = 0; i <=n; ++ i) {
        dp[i][i]=0;
        memeo[i][i]=i;
    }
    for(l=2;l<=n;l++){//遍历长度从2到n 
        for(i=1;i<=n-l+1;i++){
            j=i+l-1;
            dp[i][j]=100000000;
            for(k=i;k<j;k++){//在k处截断，分成i~k，k+1~j，两部分 
                tmp=dp[i][k]+dp[k+1][j]+dimensions[i-1]*dimensions[k]*dimensions[j];
                if(tmp<dp[i][j]){
                    dp[i][j]=tmp,memeo[i][j]=k; 
                }
            }
        }
    }
    return tmp;
}