2

晕我只是写代码来执行矩阵链乘法，可以通过动态编程解决 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);
}
4

1 回答 1

1

您使用的技术称为memoization. 大多数时候，您可以使用很少（或没有）开销的记忆来解决 DP 问题。

您的实现的复杂性就像原始的 DP 解决方案一样：O(n^3) （注意：mem数组的每个单元都应至少计算一次，并且每个单元需要 O(n) 时间来计算。单元格，不涉及任何循环，因为这将是一个简单的查找。）

另见http://en.wikipedia.org/wiki/Memoization

于 2013-05-29T12:47:12.980 回答