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


  • 0
    E

    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];
        }
    };
    

Log in to reply
 

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