算法导论矩阵链
2021-01-14 03:13
标签：算法 xdp turn 矩阵 return 循环 算法导论 col int for range从2到len： 起点0到len-range（终点range-1到len-1）: 切点从起点+1到终点: 算法导论矩阵链 标签：算法 xdp turn 矩阵 return 循环 算法导论 col int 原文地址：https://www.cnblogs.com/FdWzy/p/12943630.htmlint MatrixDP(int p[][2],int len ){ //p[i][0]、p[i][1]分别表示p[i]矩阵的行数、列数
int dp[100][100]={0};
for(int range=2;rangerange){
int _begin=0,_end=range-1; //[_begin,_end]
while(_endlen){
int cut=_begin+1;
//切成_begin,_begin+1,...,cut-1 和 cut,cut+1,...,_end两部分
dp[_begin][_end]=0x7fffffff;
while(cut_end){
dp[_begin][_end]=min(dp[_begin][_end],dp[_begin][cut-1]+dp[cut][_end]+p[_begin][0]*p[cut][0]*p[_end][1]);
++cut;
}
_begin++,_end++;
}
}
return dp[0][len-1];
}
三重for循环：