关键词：
//3d1-1 重叠子问题的递归最优解
//A1 30*35 A2 35*15 A3 15*5 A4 5*10 A5 10*20 A6 20*25
//p[0-6]=30,35,15,5,10,20,25
#include "stdafx.h"
#include <iostream>
using namespace std;
const int L = 7;
int RecurMatrixChain(int i,int j,int **s,int *p);//递归求最优解
void Traceback(int i,int j,int **s);//构造最优解
int main()
int p[L]=30,35,15,5,10,20,25;
int **s = new int *[L];
for(int i=0;i<L;i++)
s[i] = new int[L];
cout<<"矩阵的最少计算次数为："<<RecurMatrixChain(1,6,s,p)<<endl;
cout<<"矩阵最优计算次序为："<<endl;
Traceback(1,6,s);
return 0;
int RecurMatrixChain(int i,int j,int **s,int *p)
if(i==j) return 0;
int u = RecurMatrixChain(i,i,s,p)+RecurMatrixChain(i+1,j,s,p)+p[i-1]*p[i]*p[j];
s[i][j] = i;
for(int k=i+1; k<j; k++)
int t = RecurMatrixChain(i,k,s,p) + RecurMatrixChain(k+1,j,s,p) + p[i-1]*p[k]*p[j];
if(t<u)
u=t;
s[i][j]=k;
return u;
void Traceback(int i,int j,int **s)
if(i==j) return;
Traceback(i,s[i][j],s);
Traceback(s[i][j]+1,j,s);
cout<<"Multiply A"<<i<<","<<s[i][j];
cout<<" and A"<<(s[i][j]+1)<<","<<j<<endl;
//3d1-2 矩阵连乘 备忘录递归实现
//A1 30*35 A2 35*15 A3 15*5 A4 5*10 A5 10*20 A6 20*25
//p[0-6]=30,35,15,5,10,20,25
#include "stdafx.h"
#include <iostream>
using namespace std;
const int L = 7;
int LookupChain(int i,int j,int **m,int **s,int *p);
int MemoizedMatrixChain(int n,int **m,int **s,int *p);
void Traceback(int i,int j,int **s);//构造最优解
int main()
int p[L]=30,35,15,5,10,20,25;
int **s = new int *[L];
int **m = new int *[L];
for(int i=0;i<L;i++)
s[i] = new int[L];
m[i] = new int[L];
cout<<"矩阵的最少计算次数为："<<MemoizedMatrixChain(6,m,s,p)<<endl;
cout<<"矩阵最优计算次序为："<<endl;
Traceback(1,6,s);
return 0;
int MemoizedMatrixChain(int n,int **m,int **s,int *p)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
m[i][j]=0;
return LookupChain(1,n,m,s,p);
int LookupChain(int i,int j,int **m,int **s,int *p)
if(m[i][j]>0)
return m[i][j];
if(i==j)
return 0;
int u = LookupChain(i,i,m,s,p) + LookupChain(i+1,j,m,s,p)+p[i-1]*p[i]*p[j];
s[i][j]=i;
for(int k=i+1; k<j; k++)
int t = LookupChain(i,k,m,s,p) + LookupChain(k+1,j,m,s,p) + p[i-1]*p[k]*p[j];
if(t<u)
u=t;
s[i][j] = k;
m[i][j] = u;
return u;
void Traceback(int i,int j,int **s)
if(i==j) return;
Traceback(i,s[i][j],s);
Traceback(s[i][j]+1,j,s);
cout<<"Multiply A"<<i<<","<<s[i][j];
cout<<" and A"<<(s[i][j]+1)<<","<<j<<endl;
//3d1-2 矩阵连乘 动态规划迭代实现
//A1 30*35 A2 35*15 A3 15*5 A4 5*10 A5 10*20 A6 20*25
//p[0-6]=30,35,15,5,10,20,25
#include "stdafx.h"
#include <iostream>
using namespace std;
const int L = 7;
int MatrixChain(int n,int **m,int **s,int *p);
void Traceback(int i,int j,int **s);//构造最优解
int main()
int p[L]=30,35,15,5,10,20,25;
int **s = new int *[L];
int **m = new int *[L];
for(int i=0;i<L;i++)
s[i] = new int[L];
m[i] = new int[L];
cout<<"矩阵的最少计算次数为："<<MatrixChain(6,m,s,p)<<endl;
cout<<"矩阵最优计算次序为："<<endl;
Traceback(1,6,s);
return 0;
int MatrixChain(int n,int **m,int **s,int *p)
for(int i=1; i<=n; i++)
m[i][i] = 0;
for(int r=2; r<=n; r++) //r为当前计算的链长（子问题规模）
for(int i=1; i<=n-r+1; i++)//n-r+1为最后一个r链的前边界
int j = i+r-1;//计算前边界为r，链长为r的链的后边界
m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j];//将链ij划分为A(i) * ( A[i+1:j] )
s[i][j] = i;
for(int k=i+1; k<j; k++)
//将链ij划分为( A[i:k] )* (A[k+1: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;
return m[1][L-1];
void Traceback(int i,int j,int **s)
if(i==j) return;
Traceback(i,s[i][j],s);
Traceback(s[i][j]+1,j,s);
cout<<"Multiply A"<<i<<","<<s[i][j];
cout<<" and A"<<(s[i][j]+1)<<","<<j<<endl;
矩阵链相乘问题
问题描述 给定n个矩阵A1，A2,...,An，相邻的矩阵是可乘的，如何确定一个最优计算次序，使得以此次序计算需要的数乘次数最少？ 计算次序对计算性能的影响： 假设n=3，A1，A2，A3的维数分别为10×100，100×5，5×50。... 查看详情
算法之矩阵连乘
一.问题描叙 给定n个矩阵{A1，A2，……，An},其中Ai与Ai+1是可乘的，i=1，2，……，n-1。 例如： 计算三个矩阵连乘{A1，A2，A3}；维数分别为10*100,100*5,5*50 按此顺序计算需要的次数（（A1*A2）... 查看详情
c_cpp给定Ñ个顶点的多边形，每个顶点标有一个整数，每条边上标有+（加）或是×（乘）号，并且Ñ条边按照顺时针依次编号为1〜n的给出。了一个n=4个顶点的多边形。游(代码
查看详情
动态规划-矩阵连乘问题(代码片段)
...：https://www.cnblogs.com/scarecrow-blog/p/3712580.html【问题描述】给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。例如，... 查看详情
矩阵连乘问题
【问题】给定n个矩阵的链<A1,A2,…,An>，其中Ai与Ai+1是可乘的，矩阵Ai的维数为pi-1*pi（1≤i≤n），如何确定计算矩阵链乘积A1A2…An的计算次序（完全括号化方式），使得依此次序计算矩阵链乘积需要的数乘次数最少。【算法分... 查看详情
矩阵的幂运算
参考技术A0次幂是特殊的，是单位矩阵其他n次幂可以表示成（递归地）n-1次幂和自身的乘积 参考技术B幂等矩阵的主要性质：1.幂等矩阵的特征值只可能是0，1；2.幂等矩阵可对角化；3.幂等矩阵的迹等于幂等矩阵的秩，即tr（a）=r... 查看详情
矩阵链乘法(代码片段)
...g.csdn.net/c18219227162/article/details/50412333什么是矩阵链乘法？给定n个矩阵构成的一个链<A1,A2,A3,.......An>，其中i=1,2,...n，矩阵A的维数为pi-1pi，对乘积A1A2...An以一种最小化标量乘法次数的方式进行加全部括号。注：在矩阵链乘问题... 查看详情
算法导论--动态规划（矩阵链乘法）
矩阵链乘法问题给定一个n个矩阵的序列?A1,A2,A3...An?langleA_1,A_2,A_3...A_n
angle,我们要计算他们的乘积：A1A2A3...AnA_1A_2A_3...A_n。因为矩阵乘法满足结合律，加括号不会影响结果。可是不同的加括号方法。算法复杂度有非常大的区别：考... 查看详情
矩阵链乘（递归求解）
...整数n，表示矩阵的个数。 第二行包含n+1个数，表示给定的矩阵。输出格式 输出一个整数，表示最少的运算次数。样例输入3110520样 查看详情
c_cpp对于给定序列a1，a2，a3......an，寻找它的某个连续子段，使得其和最大。如（-2,11，-4,13，-5，-2）最大子段是11，-4,13其和为20.下述算法的时间复杂(代码片段)
查看详情
算法提高矩阵乘法区间dp
...整数n，表示矩阵的个数。 第二行包含n+1个数，表示给定的矩阵。输出格式 输出一个整数，表示最少的运算次数。样例输入3110520样例 查看详情
矩阵最优连乘问题（区间dp+记忆化）(代码片段)
...人们自然会提出矩阵连乘积的最优计算次序问题，即对于给定的相继n个矩阵A1,A2,…,An(其中Ai的维数为pi-1×pi，i=1,2,…,n)，如何确定计算矩阵连乘积A1A2…An的一个计算次序(完全加括号方式 查看详情
c_cpp给定Ñ个作业的集合j1，j2，......，jn。每个作业必须先由机器1处理，然后由机器2处理。作业籍需要机器ĵ的处理时间为tji。对于一个确定的作业调度，设fji是作业我在(代码
查看详情
c_cpp给定Ñ个作业的集合j1，j2，......，jn。每个作业必须先由机器1处理，然后由机器2处理。作业籍需要机器ĵ的处理时间为tji。对于一个确定的作业调度，设fji是作业我在(代码
查看详情
矩阵乘法的分解
对于z*n的矩阵a1,a2,b1,b2有：Q=(a1,a2)*(b1,b2)^T=a1*b1+a2*b2.其中，Q是n*n的矩阵。论证：1. 矩阵符合分解、分配律：A*B=A*(B1+B2)=A*B1+A*B2,其中B=B1+B2,且B,B1,B2是维度相同的矩阵。2.(a1,a2)*(b1,0)^T=(a1,0)*(b1,0)^T+(0,a2)*(b1,0)^T=a1*b1^T+0=a 查看详情
动态规划—矩阵链乘法
矩阵链乘问题描述给定n个矩阵构成的一个链<A1,A2,A3,.......An>，其中i=1,2,...n，矩阵A的维数为pi-1pi，对乘积A1A2...An 以一种最小化标量乘法次数的方式进行加全部括号。注意：在矩阵链乘问题中，实际上并没有把矩阵相乘，... 查看详情
在matlab中,a^2与a.^2结果有啥不同?
A^2是矩阵的相乘，A.^2是矩阵的数乘。矩阵的相乘是这样定义的：只有当矩阵A的列数与矩阵B的行数相等时A×B才有意义。一个m×n的矩阵a（m,n)左乘一个n×p的矩阵b（n,p)，会得到一个m×p的矩阵c（m,p)。矩阵是数乘是两个矩阵中对应... 查看详情
c_cpp找到具有给定约束的矩阵中的最长路径(代码片段)
查看详情