В чем огромная разница в производительности для двух версий кода?

Версия 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];

}