c++ - 在使用数组时使用 vector 容器挂起可快速计算2D数组

Question

我从leetcode看到了一个示例，并查看了我尝试使用vector在C++中实现它的解决方案，如下所示，

class Solution {
public:
  int minScoreTriangulation(std::vector<int>& A) {
    std::vector<std::vector<int>> memo(A.size(), std::vector<int>(A.size(), 0));
    return tri(A, 0, A.size() - 1, memo);
    }
    
  int tri(std::vector<int>& A, int i, int k, std::vector<std::vector<int>> memo) {
        if( k - i < 2) return 0;
        if( k - i == 2) return A[i] * A[i+1] * A[k];
        if( memo[i][k] != 0) return memo[i][k];
        int min = ((unsigned int) ~0) >> 1; // max positive number
        for(int j = i + 1; j < k; j++) {
          min = std::min(A[i] * A[j] * A[k] + tri(A, i, j, memo) + tri(A, j, k, memo), min);
        }
        memo[i][k] = min;
        return min;
    }
};

该程序可以在较小的输入上运行，但可以挂起以获取较大的输入，

int main() {
  std::vector<int> v0 = {35,73,90,27,71,80,21,33,33,13,48,12,68,70,80,36,66,3,70,58}; // hangs
  std::vector<int> v1 = {3,7,4,5}; // works fine
  Solution t = Solution();
  std::cout << t.minScoreTriangulation(v0) << std::endl;
  return 0;
}

因此，我使用了二维数组，并且它计算v0的速度更快。

class Solution {
public:
  int minScoreTriangulation(std::vector<int>& A) {
    int** memo = new int*[A.size()];
    for(int i=0; i<A.size(); i++) memo[i] = new int[A.size()]{0};
    
    return tri(A, 0, A.size() - 1, memo);
    }
    
  int tri(std::vector<int>& A, int i, int k, int** memo) {
        if( k - i < 2) return 0;
        if( k - i == 2) return A[i] * A[i+1] * A[k];
        if( memo[i][k] != 0) return memo[i][k];
        int min = ((unsigned int) ~0) >> 1; // max positive number
        for(int j = i + 1; j < k; j++) {
          min = std::min(A[i] * A[j] * A[k] + tri(A, i, j, memo) + tri(A, j, k, memo), min);
        }
        memo[i][k] = min;
        return min;
    }
};

是否可以使vector在合理的时间内运行？还是取决于其他因素，例如缓存？

Answer 1

问题是您通过值而不是通过引用传递std::vector<std::vector<int>>:

int tri(std::vector<int>& A, int i, int k, 
        std::vector<std::vector<int>> memo) // <-- Passed by value

每次传递memo时，都会产生一个副本。
也许一个非常聪明的优化编译器可以优化副本，但是您不能依靠它。相反，请告知您的意图:

int tri(std::vector<int>& A, int i, int k, 
        std::vector<std::vector<int>>& memo) // <-- Now passed by reference