When DP Gets Messy: A Student's Journey Through Delete and Earn
A dialogue between Professor Chen and Alex, a senior Computer Science student, as they unravel why some DP problems resist the standard recursive → memoization → tabulation pipeline.
The Student's Confusion
Alex: [walks into office hours with laptop open] Professor Chen, I'm really confused about this LeetCode problem I'm working on. I thought I understood DP, but something's not clicking.
Professor Chen: Let's see what you've got. Walk me through it.
Alex: It's LC 740: Delete and Earn. Here's the problem:
You are given an integer array nums. You want to maximize the number of points you get by performing the following operation any number of times:
- Pick any
nums[i]and delete it to earnnums[i]points. Afterwards, you must delete every element equal tonums[i] - 1and every element equal tonums[i] + 1.
Return the maximum number of points you can earn by applying the above operation some number of times.
Example 1: nums = [3,4,2]
Input: nums = [3,4,2]
Output: 6
Explanation:
- Delete 4 to earn 4 points. Consequently, 3 is also deleted. nums = [2].
- Delete 2 to earn 2 points. nums = [].
You earn a total of 6 points.
Example 2: nums = [2,2,3,3,3,4]
Input: nums = [2,2,3,3,3,4]
Output: 9
Explanation:
- Delete a 3 to earn 3 points. All 2's and 4's are also deleted. nums = [3,3].
- Delete a 3 again to earn 3 points. nums = [3].
- Delete a 3 once more to earn 3 points. nums = [].
You earn a total of 9 points.
Constraints:
1 <= nums.length <= 2 * 10^41 <= nums[i] <= 10^4
The Student's Approach
Alex: So I immediately thought: "This is a maximization problem with constraints - it's a decision tree!" At each number, I can either take it or skip it. Taking it means I earn ALL occurrences but lose access to adjacent values. That screams recursion to me!
Professor Chen: Good intuition. Show me what you wrote.
Alex: Here's my recursive solution:
class Solution {
public int deleteAndEarn(int[] nums) {
return func(0, 0, nums);
}
int func(int index, int totalVal, int[] nums) {
// Base case
// If we don't have any number left to process, then return totalVal
if (nums.length == 0) {
return totalVal;
}
if (index >= nums.length) {
return totalVal;
}
// Take it - earn ALL occurrences of this number
int currentElement = nums[index];
int earnedPoints = 0;
for (int num : nums) {
if (num == currentElement) {
earnedPoints += num;
}
}
int a = func(0, totalVal + earnedPoints, removeElement(nums, currentElement));
// Leave it
int b = func(index + 1, totalVal, nums);
return Math.max(a, b);
}
// A method for removing all the numbers that are equal to element+1 and element-1
public static int[] removeElement(int[] arr, int element) {
// Count how many elements to keep
int count = 0;
for (int num : arr) {
if (num != element + 1 && num != element - 1 && num != element) {
count++;
}
}
// Create a new array with the correct size
int[] newArr = new int[count];
int idx = 0;
for (int num : arr) {
if (num != element + 1 && num != element - 1 && num != element) {
newArr[idx++] = num;
}
}
return newArr;
}
}
Professor Chen: [nods thoughtfully] I see. And what's bothering you about this?
The Core Confusion
Alex: Well, here's the thing. I've been taught this progression: unoptimized recursion → memoization → tabulation. And I thought I was doing a DP solution, but... [gestures at screen] ...I realized we don't have something like dp[i] in my solution.
I'm confused because:
- I thought this was supposed to be a DP problem
- Even in a memoization-optimized version, we won't have something simple like
dp[i] = ..., right? - I learned that to create a DP solution, I should: create unoptimized → add memoization → THEN think about tabulation, because at that point I have solid understanding and the recursive solution guides me
But here's what's bothering me: I've seen that when recursive solutions convert to DP, they're quite similar - you almost just remove the recursive function call and put in a dp array. Their structure is nearly identical.
Professor Chen: [leans back with a knowing smile] Ah, Alex. You've just discovered one of the most important lessons in DP that textbooks often gloss over. Let me explain.
The Professor's Explanation
Your Understanding is MOSTLY Correct, But...
Professor Chen: You've identified a critical insight: your recursive solution doesn't naturally map to a simple dp[i] array. Let me show you why, and what this means about DP in general.
The Two Faces of DP
Professor Chen: There are actually two broad patterns in DP problems:
Pattern 1: "Clean" DP (What you expected)
Professor Chen: This is what you've seen in most textbook examples - Fibonacci, for instance:
// Recursive (Fibonacci example)
int fib(int n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2);
}
// Memoization - Direct mapping!
int fib(int n, int[] memo) {
if (n <= 1) return n;
if (memo[n] != -1) return memo[n];
return memo[n] = fib(n-1, memo) + fib(n-2, memo);
}
// Tabulation - Almost identical structure!
int fib(int n) {
int[] dp = new int[n+1];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2]; // Same recurrence!
}
return dp[n];
}
Alex: Right! That's exactly what I expected. The structure stays almost identical.
Professor Chen: Exactly. Why is it clean? Because the state is just n. Simple indexing. Direct translation from recursion to array.
Pattern 2: "Complex State" DP (Your situation)
Professor Chen: Now look at your recursive solution:
// Your recursive solution
int func(int index, int totalVal, int[] nums) {
// State depends on:
// 1. Current index
// 2. Accumulated total
// 3. THE ENTIRE REMAINING ARRAY (nums changes!)
}
Alex: [eyes widening] Oh...
Professor Chen: See the problem?
Alex: The state isn't just index - it's (index, totalVal, nums). And nums itself changes in recursive calls when I remove elements!
Professor Chen: Precisely! You can't easily create dp[index] because the meaning of index changes as the array shrinks. This creates a complex, multi-dimensional state space that doesn't map cleanly to an array.
Why Your Approach Makes Memoization Hard
Professor Chen: Let's think about what memoization would look like for your approach:
// What would memoization look like?
Map<String, Integer> memo = new HashMap<>();
int func(int index, int totalVal, int[] nums, Map<String, Integer> memo) {
// Create a key that captures the ENTIRE state
String key = index + "," + totalVal + "," + Arrays.toString(nums);
if (memo.containsKey(key)) return memo.get(key);
// ... rest of your logic
int result = Math.max(a, b);
memo.put(key, result);
return result;
}
Alex: That looks... messy.
Professor Chen: It is! Look at the problems:
- ❌ Key generation is expensive (converting array to string)
- ❌ The array changes drastically between calls - you get few cache hits
- ❌ Memory explosion - each unique array configuration needs storage
- ❌ Not easily convertible to tabulation - no clear
dp[i]structure
Alex: So my approach technically works, but it's fighting against the natural structure of the problem?
Professor Chen: Exactly! You're working too hard. Let me show you the right mental model.
The Right Mental Model
Professor Chen: You ARE thinking in DP terms, but your recursive approach is:
"Process array, making decisions about each element"
This works, but the state is too complex.
The standard DP approach for this problem is:
"Transform the problem first, THEN apply DP"
Alex: Transform? What do you mean?
Professor Chen: Watch this transformation:
// Original problem
nums = [2, 2, 3, 3, 3, 4]
↓
// Transform to points array
points = [0, 0, 4, 9, 4]
where points[i] = total points if we take all i's
↓
// Now it's House Robber!
dp[i] = Math.max(dp[i-1], dp[i-2] + points[i])
Alex: [pause] Wait... it's House Robber in disguise?
Professor Chen: [smiling] Now you see it! Once you transform the input:
- Taking value
3blocks values2and4 - Just like robbing house
3blocks robbing houses2and4 - The adjacency constraint is identical!
The Learning Path Revelation
Alex: So when I said "create unoptimized → memoization → then think about DP"... was I wrong?
Professor Chen: No, you weren't mistaken - your learning path is solid! But you've discovered an important edge case:
Your path works WHEN:
- ✅ State naturally maps to simple parameters (like
dp[i],dp[i][j]) - ✅ Recursive calls have overlapping subproblems with same state
- ✅ State space is manageable
It breaks down WHEN:
- ❌ State includes complex objects (like entire arrays)
- ❌ Problem needs transformation first
- ❌ Recursive structure doesn't match the optimal DP state
Alex: So for Delete and Earn specifically...
Professor Chen: Let me map it out for you:
Your Approach:
State: (index, totalVal, modified_array)
↓
Complex, hard to memoize
↓
Not easily → tabulation
Standard Approach:
Transform problem first:
nums → points array
↓
State: just index i
↓
dp[i] = max(dp[i-1], dp[i-2] + points[i])
↓
Clean House Robber pattern
The Key Takeaway
Alex: So sometimes I need to transform the problem before the standard DP pattern emerges?
Professor Chen: Exactly! Not every recursive solution converts cleanly to dp[i] = .... When your state is complex, it's nature's way of telling you to rethink the problem representation.
Alex: What should I do with my current solution?
Professor Chen: You have two options:
Option 1: Force memoization on your approach (not recommended)
// Use HashMap with complex keys
// Will work but slow and messy
Option 2: Learn the transformation (recommended)
// Step 1: Transform problem
int maxVal = 0;
for (int num : nums) maxVal = Math.max(maxVal, num);
int[] points = new int[maxVal + 1];
for (int num : nums) {
points[num] += num; // Sum all occurrences
}
// Step 2: NOW it's clean DP (House Robber)
// dp[i] represents: max points using numbers 0...i
int[] dp = new int[maxVal + 1];
dp[0] = points[0];
dp[1] = Math.max(points[0], points[1]);
for (int i = 2; i <= maxVal; i++) {
dp[i] = Math.max(
dp[i-1], // Skip value i
dp[i-2] + points[i] // Take value i (skip i-1)
);
}
return dp[maxVal];
Alex: [typing notes furiously] This is brilliant! Now I can do:
- Recursive with simple state
- Memoization with
dp[i] - Tabulation with same structure
All because I transformed the problem first!
Final Wisdom
Professor Chen: [standing up] Alex, your confusion revealed deep insight. Remember this:
Not all problems convert directly from recursion → memoization → tabulation.
Sometimes you need to massage the problem first to reveal the DP structure. The best DP solutions often come from:
- Recognizing the problem's true nature
- Transforming it into a known pattern
- THEN applying the standard DP pipeline
Your recursive solution wasn't wrong - it was solving a harder problem than necessary!
Alex: [packing up laptop] This makes so much sense now. I was solving the problem in "hard mode" when there was an elegant transformation waiting to be discovered.
Professor Chen: That's the art of DP, Alex. Sometimes the hardest part isn't the DP itself - it's seeing which problem you're actually solving.
Alex: Thank you, Professor. I'm going to rewrite this with the transformation approach!
Professor Chen: [smiling] That's what I like to hear. And Alex? When you're stuck on a DP problem and the state feels messy - that's often a clue that you're missing a transformation. Listen to that feeling.
Epilogue
Alex left office hours that day with more than just a solution to Delete and Earn. They learned that the most elegant DP solutions often hide behind problem transformations, and that sometimes the "obvious" recursive approach, while correct, might be solving a harder problem than necessary.
The next week, Alex came back with three more problems they'd solved by first looking for transformations. Professor Chen just smiled and said, "Now you're thinking like a DP expert."
Further Reading
- House Robber - The Pattern 1b Journey
- Pattern 1: Linear Sequence Decision Problems
- Pattern 1b: Selection with Skip Constraint
Tags: #dynamic-programming #transformation #house-robber-pattern #problem-solving #learning-journey