Classic Edit Distance ( DP )

Problem Description:
Given 2 strings, output the minimal edit distance between them. There are 3 valid operations, each with cost of 1.
1. Delete a character.
2. Insert a character.
3. Replace a character.
The objective is to make both strings identical.

Solution:
First we should know that if inserting some character at some point is optimal, the cost will not change for deleting the character that corresponds. Therefore we can neglect operation 2.
Let us attempt a recursive function that reduces problems into smaller subproblems.
dp[ i ][ j ] = minimal edit distance of A[ 0 , i ) and B[ 0, j ).
dp[ i ][ j ] = 0, if( i == 0 and j == 0 )
min{ dp[ i - 1 ][ j ] + 1, dp[ i ][ j - 1 ] + 1, dp[ i - 1 ][ j - 1 ] ( if A[ i - 1 ] == A[ j - 1 ] ), dp[ i - 1 ][ j - 1 ] + 1 }, otherwise
For the first value in min{}, it is equivalent to deleting the last character in A, the second equivalent to deleting the last character in B, the third taking both last characters as matched, and the last for replacing.

void solve(){
    string A, B; cin >> A >> B;
    vvi dp( A.size() + 1, vi( B.size() + 1, 1e9 ) );
    vvp pre( A.size() + 1, vp( B.size() + 1, pii( -1, -1 ) ) );
    dp[ 0 ][ 0 ] = 0;
    for( int i = 0; i <= A.size(); ++i )
        for( int j = 0; j <= B.size(); ++j ){
            if( i < A.size() ){
                if( upmin( dp[ i + 1 ][ j ], dp[ i ][ j ] + 1 ) )
                    pre[ i + 1 ][ j ] = pii( i, j );
            }
            if( j < B.size() ){
                if( upmin( dp[ i ][ j + 1 ], dp[ i ][ j ] + 1 ) )
                    pre[ i ][ j + 1 ] = pii( i, j );
            }
            if( i < A.size() and j < B.size() ){
                if( A[ i ] == B[ j ] ){
                    if( upmin( dp[ i + 1 ][ j + 1 ], dp[ i ][ j ] ) )
                        pre[ i + 1 ][ j + 1 ] = pii( i, j );
                } else{
                    if( upmin( dp[ i + 1 ][ j + 1 ], dp[ i ][ j ] + 1 ) )
                        pre[ i + 1 ][ j + 1 ] = pii( i, j );
                }
            }
        }
    cout << dp[ A.size() ][ B.size() ] << endl;
}