这两个版本的代码的巨大性能差异在哪里?

Question

我正在研究一个问题给定一个字符串s，分区s使得分区的每个子字符串都是回文。

返回s的回文分割所需的最小切割。这个问题也可以在这里找到。https://oj.leetcode.com/problems/palindrome-partitioning-ii/

版本1是我在网上找到的解决方案的一个版本。

版本2是我的代码。

它们似乎以非常相似的方式工作。然而，对于相当大的输入，版本2需要超过6000毫秒，而版本1大约需要71毫秒。

谁能提供任何想法的时差是从哪里来的?

版本1:

int minSol(string s) {
   int len = s.size();
   vector<int> D(len + 1);
   vector<vector<int>> P;
   for (int i = 0; i < len; i++){
         vector<int> t(len);
         P.push_back(t);
   }
   for (int i = 0; i <= len; i++)
         D[i] = len - i;
   for (int i = 0; i < len; i++)
         for (int j = 0; j < len; j++)
                P[i][j] = false;
   for (int i = len - 1; i >= 0; i--){
       for (int j = i; j < len; j++){
           if (s[i] == s[j] && (j - i < 2 || P[i + 1][j - 1])){
               P[i][j] = true;
               D[i] = min(D[i], D[j + 1] + 1);
                }
         }
}
   return D[0] - 1;
}

版本2:

int minCut(string s) {
   int size = s.size();
   vector<vector<bool>> map;
   for (int i = 0; i < size; i++){
         vector<bool> t;
         for (int j = 0; j < size; j++){
                t.push_back(false);
         }
         map.push_back(t);
   }
   vector<int> minCuts;
   for (int i = 0; i < size; i++){
         map[i][i] = true;
         minCuts.push_back(size - i - 1);
   }
   for (int i = size - 1; i >= 0; i--){
         for (int j = size - 1; j >= i; j--){
                if (s[i] == s[j] && (j - i <= 1 || map[i + 1][j - 1])){
                       map[i][j] = true;
                       if (j == size - 1){
                             minCuts[i] = 0;
                       }else if (minCuts[i] > minCuts[j + 1] + 1){
                             minCuts[i] = minCuts[j + 1] + 1;
                       }
                }
         }
   }
   return minCuts[0];
}

Answer 1

我猜这是因为在第二个版本中你做的是size ^2 push_back 's，而在第一个版本中你只做size push_back 's。