mediumCodingConceptMidSenior
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.
The state is unchanged - the minimum cost to transform the first i characters of one string into the first j of the other - because the subproblem structure does not depend on what operations cost. Only the recurrence changes, adding a per-operation weight instead of a uniform 1, and the base cases become multiples of the insert and delete costs rather than i and j.
4 min readUpdated 2026-08-16Target archetype: Big Tech, Product Startup, Enterprise Captive
Answer
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.
Was this answer helpful?
Likely follow-ups
- Replace costs 3 but delete plus insert costs 3 as well. Does your recurrence still do the right thing?
- Reduce the space to O(min(m, n)) and tell me what you lose.
- How would you reconstruct the actual sequence of operations, not just the cost?
- Add a transposition operation for swapping adjacent characters. What changes?
- Why is the table (m+1) by (n+1) rather than m by n?
Related questions
- Assign n tasks to n workers at minimum cost, with n up to 20. Why a bitmask, and what does it cost?hardAlso on dynamic-programming4 min
- Find the cheapest flight from one city to another using at most K stops. Why does plain Dijkstra give the wrong answer?mediumAlso on dynamic-programming5 min
- How do you know a problem is dynamic programming?mediumAlso on dynamic-programming5 min
- Envelopes nest only when both width and height are strictly larger. How many can you nest, and why must equal widths be sorted by height descending?hardAlso on dynamic-programming4 min