Deletion Distance problem on Pramp

deletionDistance.cpp

#include <iostream>
#include <string>

using namespace std;

// i: str1
// j: str2
int calcDeletionDistance(string str1, string str2, int i, int j, int dp[][2000]) {
  
  if (i == str1.length()) {
    return dp[i][j] = str2.length() - j;
  }
  else if (j == str2.length()) {
    return dp[i][j] = str1.length() - i;
  }
  
  if (dp[i][j] != -1) {
    return dp[i][j];
  }
  
  if (str1[i] == str2[j]) {
    return dp[i][j] = calcDeletionDistance (str1, str2, i + 1, j + 1, dp);
  }
  
  return dp[i][j] = 1 + min (calcDeletionDistance (str1, str2, i + 1, j, dp), calcDeletionDistance (str1, str2, i, j + 1, dp));
  
}


int deletionDistance( const string& str1, const string& str2 ) {
  int len1 = str1.length(), len2 = str2.length();
  int dp[len1][2000];
  for (int i = 0; i < len1; i ++) {
    for (int j = 0; j < len2; j ++) {
      dp[i][j] = -1;
    }
  }
  return calcDeletionDistance(str1, str2, 0, 0, dp);
}

int main() {
  
  
  string s1, s2;
  cin >> s1 >> s2;
  
  cout << deletionDistance (s1, s2) << endl;
  
  return 0;
  
}