dp 最优矩阵乘法

小咪咪 2022-06-13 08:42 206阅读 0赞

该题题意如下

描述

有若干个矩阵\{Ai\}，元素都为整数且已知矩阵大小。

如果要计算所有矩阵的乘积A1 \* A2 \* A3 .. Am，最少要多少次整数乘法？

输入

第一行一个整数n(n <= 100)，表示一共有n-1个矩阵。  
第二行n个整数B1, B2, B3... Bn(Bi <= 100)，第i个数Bi表示第i个矩阵的行数和第i-1个矩阵的列数。  
等价地，可以认为第j个矩阵Aj(1 <= j <= n - 1)的行数为Bj，列数为Bj+1。

输出

一个整数，表示最少所需的乘法次数

样例输入

6
    10 1 50 50 20 5

样例输出

3650

来源

poj 1651

该题明显是一道动态规划的题目

很容易想到 用f(i,j)来表示 从 第i个矩阵到第j个矩阵乘起来的最优结果

那么会有下面的方程 f(i,j) =min\{f(i,j), f(i,k)+f(k+1,j)+p\[i-1\]\*p\[k\]\*p\[j\]\} (i<k<j)

这个方程是很好想的，那么编程的时候怎么合理的实现呢？ 怎么保证在推导当前状态的时候用到的参数都是之前已经推导过的呢

很好想，根据i和j距离的长度从小到大推导就可以了啊

代码如下

// ConsoleApplication1.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<iostream>
    using namespace std;
    int n;
    int p[150];
    int f[150][150];
    int min(int x, int y)
    {
    	return x < y ? x : y;
    }
    int main()
    {
    	cin >> n; //n个数 n-1个矩阵
    	for (int i = 0; i < n; i++)
    		cin >> p[i];
    	n--; //这里变为n个矩阵来表示
    	int j; 
    	for (int r=2; r<=n; r++) //这里的r是多少个矩阵,至少有两个矩阵才可以乘
    		for (int i = 1; i <=(n-r+1); i++)  //这里对i限制不能使得j超过第n个矩阵
    		{
    			j = i + r - 1; //推导出j,从第i个矩阵到第j个矩阵
    			f[i][j] = f[i + 1][j] + f[i][i] + p[i - 1] * p[i] * p[j]; //很简单而且稳定的初始化
    			for (int k = i + 1; k < j; k++)
    				f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + p[i - 1] * p[k] * p[j]);
    		}
    	cout << f[1][n] << endl; 
        return 0;
    }