晕我只是写代码进行矩阵链乘,可以用动态规划来解决 http://en.wikipedia.org/wiki/Matrix_chain_multiplication#A_Dynamic_Programming_Algorithm
这是我写的代码,我觉得比维基百科提供的代码简单。所以我怀疑我是否在进行动态规划?
而且我无法计算出我的程序的时间复杂度。谁能帮我计算一下这个程序的时间复杂度?
这是我的猜测..
每次调用 for 循环都会运行 n 次?如果不使用 mem..
对于每个循环,它将扩展为两个
如果使用 mem,它会阻止重新计算... 啊啊我想不通,希望有人能帮助我:-)
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <climits>
using namespace std;
int mem[10][10];
int row[10];
int col[10];
int m[10];
#define NUM 4
int DP(int c, int r){
if(mem[c][r] != INT_MAX) return mem[c][r];
if(c == r) return 0;
int min_cost;
for(int j=c; j<r; j++){
min_cost = DP(c, j) + DP(j+1, r) + m[c-1]*m[j]*m[r];
if(min_cost < mem[c][r])
mem[c][r] = min_cost;
}
return mem[c][r];
}
int main(){
for(int i=0; i< 10;i++){
for(int j=0; j<10;j++){
mem[i][j] = INT_MAX;
}
}
int n = NUM; // MAX 4 matrix
int a,b;
for(int i=0; i< NUM+1; i++){
cin >> a;
m[i] = a;
}
cout << "Lowest Cost for matrix multiplicatoin " << DP(1,NUM);
}
最佳答案
您使用的技术称为内存
。大多数时候,您可以使用记忆化来解决 DP 问题,而开销很小(或没有)。
你的实现的复杂度就像原来的 DP 解决方案:O(n^3) n) 要计算的时间。单元格的进一步计算不涉及任何循环,因为这将是一个简单的查找。)
关于algorithm - 我在使用动态规划吗? c中的矩阵链乘法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16812295/