редактировать расстояние с помощью дп с памяткой - PullRequest
Новая
       45

редактировать расстояние с помощью дп с памяткой

0 голосов
/ 29 апреля 2019

Я закодировал dp с памяткой для расстояния редактирования, но он отличается от решения, предоставленного в geeksforgeeks (также dp с памяткой). Ниже моя версия кода и код сайта geeksforgeeks: 

 //my version of code
 int dist(string X, int m, string Y, int n)
{
    // base case: empty strings (case 1)
    if (m == 0)
        return n;

    if (n == 0)
        return m;
        if (dp[m][n] != -1)
                return dp[m][n];
    int cost;

    // if last characters of the strings match 
    if (X[m - 1] == Y[n - 1])
        cost = 0;
    else
        cost = 1;

    return min (min(dist(X, m - 1, Y, n) + 1,   
          dist(X, m, Y, n - 1) + 1),                     
                      dist(X, m - 1, Y, n - 1) + cost); 
}

Это решение Geeksforgeeks. Я прокомментировал, какая часть сбивает с толку 

//geeksforgeeks solution



/*i am not able to understand this portion of code*/
    if (dp[m - 1][n - 1] != -1) //why they used m-1,n-1 instead of just m,n
        return dp[m - 1][n - 1]; 


    if (str1[m - 1] == str2[n - 1]) 
        return dp[m - 1][n - 1] = editDist(str1, str2, m - 1, n - 1, dp); 
  return dp[m - 1][n - 1] = 1 + min(editDist(str1, str2, m, n - 1, dp), // 
                                  editDist(str1, str2, m - 1, n, dp), // 
                                  editDist(str1, str2, m - 1, n - 1, dp) //  
                                  ); 
}
...