Edit Distance - Transition

At position $(i,j)$, compare $A[i]$ with $B[j]$: If they match: No operation needed. $dp[i][j] = dp[i-1][j-1]$. If they don't match, choose the cheapest:

• Replace $A[i]$ with $B[j]$: $dp[i-1][j-1] + 1$ • Delete $A[i]$: $dp[i-1][j] + 1$ • Insert $B[j]$: $dp[i][j-1] + 1$ The transition is the core of any DP solution. All $3$ operations pull from previously computed cells, so filling the table row by row produces correct results.