EditDistance (DP)

Topic: 11. Dynamic Programming

1. Define State

• Definition: What does dp[i] represent?
• State Variables: (e.g., index, weight, capacity)

2. Recurrence Relation

40196 f(n) = ... 40196

3. Base Cases

• [ ] Smallest valid input?
• [ ] Initialization (e.g., dp[0] = 1)

4. Complexity

• Time: O(?)
• Space: O(?)
• [ ] Can we optimize space?

5. Code

package com.dsa.dynamic_programming;

import java.util.*;

public class EditDistance {
    public void solve() {
        // TODO: Implementation
    }
}