LeetCode 72 Edit Distance - Transition

At position $(i, j)$, compare A[i-1] and B[j-1]. If they match: $dp[i][j] = dp[i-1][j-1]$. No operation needed. If they don't match: $dp[i][j] = 1 + \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])$ That's delete, insert, and replace respectively.

Each costs 1. The final answer is $dp[m][n]$. The formula is the core of any DP solution. It defines how dp[i][j] depends on earlier dp values. Getting this formula right is often the hardest and most rewarding part.