动态规划算法矩阵乘法公式

❶ 要比赛了，急求一道动态规划题的矩阵乘法解法！

注意到M<=5，状态可以用0..31表示。计算每个状态之间的 相容关系，构成一个有向图。

这时转化成一个图论问题：求1111..111到111.11111的长为N的路径总数。

可以用矩阵做。

矩阵有一个性质，自乘N次后，元素（i,j）表示由I到J的长度为N的路径数。

program p1194;
type
matrix=array[0..31,0..31]of longint;
var
n,m,p:longint;
mm:array[0..70]of matrix;
ans:matrix;
pow:array[0..30]of longint;

function harmony(a,b:byte):boolean;
var
k,i:byte;
begin
for i:=1 to n do
if (a shr (i-1) and 1=0) then
begin
if (b shr (i-1) and 1=0) then exit(false);
b:=b xor (1 shl (i-1));
end;

i:=1;
while i<=n do
begin
if (b shr (i-1) and 1=1)then
begin
if (b shr (i-1)) and 3<>3 then exit(false);
i:=i+2;
end
else inc(i);
end;

exit(true);
end;

procere makematrix;
var
i,j:byte;
begin
for i:=0 to (1 shl n)-1 do
for j:=0 to (1 shl n)-1 do
if harmony(i,j) then mm[0][i,j]:=1;
end;

procere mul(var ma:matrix;t,u:matrix);
var
i,j,k:byte;
begin
fillchar(ma,sizeof(ma),0);
for i:=0 to 1 shl n-1 do
for j:=0 to 1 shl n-1 do
for k:=0 to 1 shl n-1 do
ma[i,j]:=(ma[i,j]+t[i,k]*u[k,j])mod p;
end;

procere main;
var
k,i,now:longint;
begin
pow[0]:=1;
for i:=1 to 30 do pow[i]:=pow[i-1]*2;
now:=1;k:=0;
while now<=m do
begin
now:=now*2;inc(k);
mul(mm[k],mm[k-1],mm[k-1]);
end;
now:=m-1;ans:=mm[0];

for i:=k downto 0 do
begin
if now>=pow[i] then
begin
mul(ans,ans,mm[i]);
now:=now-pow[i];
end;
if now=0 then break;
end;

writeln(ans[(1 shl n)-1,(1 shl n)-1]);
end;

begin
readln(m,n,p);
fillchar(mm,sizeof(mm),0);
makematrix;
main;
end.

❷ 矩阵间的乘法公式

如果C=AB的话,C中第a行b列的数为A的第a行乘上B的第b列
比如说A=|a1 a2| B=|b1 b2|
|a3 a4| B=|b3 b4|
那么C=|a1*b1+a2*b3 a1*b2+a2*b4|
|a3*b1+a4*b3 a3*b2+a4*b4|
所以说如果是一个x1行x2列的矩阵乘上一个y1行y2列的矩阵,结果将是一个x1行y2列的矩阵

❸ 矩阵乘法算法详细过程

= 1*2 + (-1)*1 + 0*3 = 1

❹ 矩阵乘法算法

int A[N][N];
int B[N][N];
int C[N][N];

for(int* pA = a, *pB = B, *pC = C; pA != B + N*N; ++pA, ++pB, ++pC)
{
*pC = *pA * *pB;
}

复杂度O(3N^2)

❺ 求大神用动态规划算法求解矩阵连续相乘下图效果

#include<stdlib.h>
#include<stdio.h>

#define N 5
void Print_OPTIMAL_PARENS(int s[N+1][N+1],int i,int j) //定义函数打印最优全括号的结果
{
if(i==j)
printf("A%d",i);
else
{
printf("(");
Print_OPTIMAL_PARENS(s,i,s[i][j]); //在分裂处进行递归调用
Print_OPTIMAL_PARENS(s,s[i][j]+1,j);
printf(")");
}
}
int main()
{
int matrix[N+1]; //matrix中记录矩阵的维数
int i,j,k,q;
int m[N+1][N+1]; //m中记录矩阵连乘的次数
int s[N+1][N+1]; //s[i][j]中记录了对Ai...Aj进行分裂的最优的k值

for(i=0;i<=N;i++)
scanf("%d",&matrix[i]);

for(j=1;j<=N;j++)
for (i=j;i>=1;i--) //当i=j时,m[i][j]=0，
{ //当i<j时,m[i][j]=min{m[i][k]+m[k+1][j]+p(i-1)p(k)p(j)} i=<k<j
if (j==i)
m[i][j]=0;
else
{
m[i][j]=600000;
for (k=i;k<j;k++)
{
q=m[i][k]+m[k+1][j]+matrix[i-1]*matrix[k]*matrix[j];
if (q<m[i][j])
{
m[i][j]=q;
s[i][j]=k;
}
}
}
}
printf("计算得到的矩阵为： ");
for(i=1;i<=N;i++)
{
for (j=1;j<i;j++)
printf(" ");
for (j=i;j<=N;j++)
printf(" %d",m[i][j]);
printf(" ");
}
printf("矩阵连乘所需要的最少数量乘法次数为：%d ",m[1][N]);
//Print_OPTIMAL_PARENS(s,1,N);
return 0;
}

❻ 矩阵乘法公式

|a11 a12 …… a1n||b11 b12 …… b1k|

|a21 a22 …… a2n||b21 b22 …… b2k|=

| . . …… . || . . …… . |

|am1 am2 …… amn||bn1 bn2 …… bnk|

|a11*b11+a12*b21+……+a1n*bn1 a11*b12+a12*b22+……+a1n*bn2

若A、B和C表示三个矩阵并有C=AB，A为n行m列，B为m行q列，则C为n行q列

则对于C矩阵任版一元素Cij都有权

Cij=ai1*b1j+ai2*b2j+ai3*b3j+...+ain*bnj

i=1,2,3,...,n,j=1,2,3,...q

(6)动态规划算法矩阵乘法公式扩展阅读：

1、当矩阵A的列数（column）等于矩阵B的行数（row）时，A与B可以相乘。

2、矩阵C的行数等于矩阵A的行数，C的列数等于B的列数。

3、乘积C的第m行第n列的元素等于矩阵A的第m行的元素与矩阵B的第n列对应元素乘积之和。

❼ 动态规划 矩阵连乘 c语言

#include <stdio.h>
#include <limits.h>
#include<stdlib.h>
#define LENGTH 6

void MatrixChainOrder(int p[],int m[][LENGTH],int s[][LENGTH])
{
int n=LENGTH;
int i,j,k,r,t;
for(i=0;i<n;i++)
m[i][i]=0;
for( r=1;r<n;r++)
{
for(i=0;i<n-r;i++)
{

j=i+r;
m[i][j]=m[i][i]+m[i+1][j]+p[i]*p[i+1]*p[j+1];
s[i][j]=i;
for(k=i+1;k<j;k++)
{
t=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1];
printf("t=%d;,m[%d][%d]=%d\n",t,i,j,m[i][j]);
if(t<m[i][j])
{
m[i][j]=t;
s[i][j]=k;
}
}

}

}
}
int main()
{
int p[] = {30,35,15,5,10,20,25};
int m[LENGTH][LENGTH];
int s[LENGTH][LENGTH];
int i,j,k;
MatrixChainOrder(p,m,s);
printf("最少数乘次数：\n");
for(i = 0;i<LENGTH;i++)
{ for(j = 0 ;j<=i ;j++ )
printf(" ");
for(k = i; k<LENGTH;k++)
printf("%8d",m[i][k]);
printf("\n");
}
printf("断开位置：\n");
for(i = 0;i<LENGTH;i++)
{ for(j = 0 ;j<=i ;j++ )
printf(" ");
for(k = i; k<LENGTH;k++)
printf("%4d",s[i][k]);
printf("\n");
}

system("Pause");
return 0;
}

❽ 矩阵乘法如何计算详细步骤!

回答：

此题2行2列矩阵乘以2行3列矩阵。

所得的矩阵是：2行3列矩阵

最后结果为： |1 3 5|

|0 4 6|

拓展资料

1、确认矩阵是否可以相乘。只有第一个矩阵的列的个数等于第二个矩阵的行的个数，这样的两个矩阵才能相乘。

图示的两个矩阵可以相乘，因为第一个矩阵，矩阵A有3列，而第二个矩阵，矩阵B有3行。

6、检查相应的数字是否出现在正确的位置。19在左下角，-34在右下角，-2在左上角，-12在右上角。

❾ 动态规划一水题，矩阵乘法！

看看08年国家集训队俞华程大牛关于矩阵乘法的论文吧。

❿ 矩阵乘法怎么算

比如乘法AB

一、

1、用A的第1行各个数与B的第1列各个数对应相乘后加起来,就是乘法结果中第1行第1列的数；

2、用A的第1行各个数与B的第2列各个数对应相乘后加起来,就是乘法结果中第1行第2列的数；

3、用A的第1行各个数与B的第3列各个数对应相乘后加起来,就是乘法结果中第1行第3列的数；

依次进行，（直到）用A的第1行各个数与B的第末列各个数对应相乘后加起来,就是乘法结果中第1行第末列的的数。

二、

1、用A的第2行各个数与B的第1列各个数对应相乘后加起来,就是乘法结果中第2行第1列的数；

2、用A的第2行各个数与B的第2列各个数对应相乘后加起来,就是乘法结果中第2行第2列的数；

3、用A的第2行各个数与B的第3列各个数对应相乘后加起来,就是乘法结果中第2行第3列的数；

依次进行，（直到）用A的第2行各个数与B的第末列各个数对应相乘后加起来,就是乘法结果中第2行第末列的的数。

依次进行，

（直到）用A的第末行各个数与B的第1列各个数对应相乘后加起来,就是乘法结果中第末行第1列的数；

用A的第末行各个数与B的第2列各个数对应相乘后加起来,就是乘法结果中第末行第2列的数；

用A的第末行各个数与B的第3列各个数对应相乘后加起来,就是乘法结果中第末行第3列的数；

依次进行，

（直到）用A的第末行各个数与B的第末列各个数对应相乘后加起来,就是乘法结果中第末行第末列的的数。

(10)动态规划算法矩阵乘法公式扩展阅读：

矩阵相乘最重要的方法是一般矩阵乘积。它只有在第一个矩阵的列数（column）和第二个矩阵的行数（row）相同时才有意义[1]。一般单指矩阵乘积时，指的便是一般矩阵乘积。一个m×n的矩阵就是m×n个数排成m行n列的一个数阵。由于它把许多数据紧凑的集中到了一起，所以有时候可以简便地表示一些复杂的模型。

参考资料：矩阵乘法_网络