This is Edit Distance from LeetCode, also called Levenshtein Distance. Given two strings, find the minimum operations to convert one to the other. You can insert, delete, or replace a character. For "horse" and "ros": horse → rorse → rose → ros. operations.
Constraints: . Brute-force recursion is exponential. Build up answers for shorter prefixes first to avoid recomputation.