Edit distance where insert costs 1, delete costs 2 and replace costs 3. Define the DP state and the recurrence, and tell me what changes from the classic version.

Short answer

The state does not change. dp[i][j] is the minimum total cost to transform the first i characters of a into the first j characters of b. Costs are weights on the transitions, not on the subproblem structure, so only the recurrence and the base cases move — each branch is charged its own cost instead of a uniform 1.

Defining the state precisely

Say it with the indices pinned down, because a vague state definition is where most incorrect recurrences originate:

dp[i][j] = minimum cost to turn a[0..i-1] into b[0..j-1].

The table is (m+1) × (n+1) rather than m × n because the empty prefix is a legitimate subproblem — you need dp[0][j], the cost of building b's first j characters from nothing. Dropping the extra row and column is the most common off-by-one in this problem, and being able to justify the +1 is a signal in itself.

Base cases carry the costs

This is the first place the weights appear, and it is where a candidate who has only memorised the classic version stumbles.

dp[0][0] = 0
dp[i][0] = i * COST_DELETE      // delete all i characters of a
dp[0][j] = j * COST_INSERT      // insert all j characters of b

In the unit-cost version these are just i and j, which hides the multiplication. With delete at 2 and insert at 1, transforming a 5-character string into the empty string costs 10, not 5. Getting this wrong produces answers that are correct in shape and wrong in value, which is harder to spot than a crash.

The recurrence

if a[i-1] == b[j-1]:
    dp[i][j] = dp[i-1][j-1]                          // free match, no operation
else:
    dp[i][j] = min(
        dp[i-1][j]     + COST_DELETE,                // drop a[i-1]
        dp[i][j-1]     + COST_INSERT,                // add b[j-1]
        dp[i-1][j-1]   + COST_REPLACE                // substitute
    )

Each branch answers one question: what was the last operation? If the last thing you did was delete a[i-1], then before it you had already solved a[0..i-2] → b[0..j-1], which is dp[i-1][j]. The insert and replace branches read the same way. Presenting the recurrence as an enumeration of the possible final operations is much more convincing than reciting three min arguments, and it makes the index directions self-checking.

The matching case is worth stating explicitly: when characters are equal you take dp[i-1][j-1] with no cost added. You do not min it against the alternatives, because no operation can be cheaper than free when costs are non-negative.

int editDistance(String a, String b, int cIns, int cDel, int cRep) {
    int m = a.length(), n = b.length();
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 1; i <= m; i++) dp[i][0] = i * cDel;
    for (int j = 1; j <= n; j++) dp[0][j] = j * cIns;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(dp[i - 1][j - 1] + cRep,
                           Math.min(dp[i - 1][j] + cDel,
                                    dp[i][j - 1] + cIns));
            }
        }
    }
    return dp[m][n];
}

The interaction the weights create

Here is the part that only exists in the weighted version, and it is usually the follow-up. With replace at 3 and delete plus insert at 2 + 1 = 3, substituting a character and deleting-then-inserting it cost exactly the same. If replace were 4, the delete-plus-insert path would be strictly cheaper and the replace branch would never be chosen.

You do not need to special-case any of this — the min already explores both, because a delete followed by an insert is reachable through dp[i-1][j] and dp[i][j-1]. But noticing that the recurrence handles it, and being able to say why the replace branch becomes dead when COST_REPLACE > COST_INSERT + COST_DELETE, demonstrates that you understand the recurrence rather than having transcribed it.

It also implies a sanity check: with unusual weights, the algorithm may report a cost lower than any sequence you would have chosen by hand, and that is correct.

Why this is optimal substructure

An optimal transformation of a[0..i-1] into b[0..j-1] ends with exactly one of: a match, a delete, an insert, or a replace. Whichever it is, the remaining prefix transformation embedded inside it must itself be optimal — otherwise you could substitute a cheaper one and beat the supposed optimum. That argument is what licenses the recurrence, and offering it unprompted is usually the difference between a mid and a senior answer.

Space, and what optimising it costs

Each row depends only on the row above and the current row, so you can hold two rows and reduce space from O(m·n) to O(min(m, n)) by iterating over the shorter string.

The cost is that you can no longer reconstruct the operation sequence. Recovering the actual edits requires walking backwards through the full table from dp[m][n], comparing each cell against its predecessors to see which branch produced it — and that table no longer exists. So the rule is: keep the full table if you need the edit script, use two rows if you only need the number. Stating that trade rather than reflexively optimising is the better answer, because interviewers frequently follow up by asking for the operations.

---

© 2026 Preptima. Originally published at preptima.com.