# Why is this code that uses optimized DP taking this long 600 ms (in the lowest 0.4%) ?

• The following code uses recursion with memoization (top-down DP). The array initialization doesn't cost much time.

Can anyone explain reason why this top-down DP is taking 600 ms whereas another solution posted at https://discuss.leetcode.com/topic/5219/dynamic-programming-solution-in-c-with-algorithm-description/2 takes only 9ms (with bottom-up DP)?

class Solution {
public:
int d[1000][1000] = {{-1}};
int minDistance(string w1, string w2) {
int sz1=w1.size(), sz2=w2.size();
//int d[sz1+1][sz2+1] = {-1};
for (int i =0; i <=sz1; i++) {
for (int j =0; j <=sz2; j++) {
d[i][j] =-1;
}
}
for (int i =0; i <=sz1; i++) d[i][sz2] =0;
for (int j =0; j <=sz2; j++) d[sz1][j] =0;
return minD(w1, w2, 0, 0);
}

int minD(string& w1, string& w2, int m, int n) {
//   cout <<" m, n "  << m << "  " << n << endl;
if (m== w1.size()) return w2.size()-n;
if (n== w2.size()) return w1.size()-m;
if (d[m][n]!= -1) return d[m][n];

int i = m, j =n;
int v11 = minD(w1, w2, i+1, j+1);

if (w1[i] == w2[j]) {
//  d[i][j] = min(v11, min(v01 +1, v10 +1));
d[i][j] = v11;
}
else {
int v01 = minD(w1, w2, i, j+1);
int v10 = minD(w1, w2, i+1, j);
d[i][j] = min( v11 +1 , min(v01 +1, v10 +1));
}
return d[m][n];
}
};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.