int f(int idx1, int idx2, vector<vector<int>> &dp, const string A, const string B){
    if(idx1 == A.size()) return B.size() - idx2; // adding all to get to B
    if(idx2 == B.size()) return A.size() - idx1; // deleting all remaining in A
    int &ans = dp[idx1][idx2];
    if(~ans) return ans;
    if(A[idx1] == B[idx2]) return ans = f(idx1 + 1, idx2 + 1, dp, A, B); // just move foward
    int insert = f(idx1, idx2 + 1, dp, A, B);
    int del = f(idx1 + 1, idx2, dp, A, B);
    int replace = f(idx1 + 1, idx2 + 1, dp, A, B);
    return ans = 1 + min(insert, min(del, replace));
}

int Solution::minDistance(string A, string B) {
    vector<vector<int>> dp(A.size(), vector<int>(B.size(),-1));
    return f(0,0, dp, A, B);
}