Guna Sai

Posted on Jun 13

No Recursion, No Table, Still DP? My Shift From Brute Force to Intuition

#programming #learning #dsa #dp

Wait... Is This Even DP?

When I started learning Dynamic Programming (DP), I thought I had it all figured out.

First write recursion ->
Then add memoization ->
Then convert to tabulation ->
And if you're feeling fancy, do space optimization.

Easy, right?

So whenever I saw a tough problem, my brain immediately went:

"Where’s the recursion? Let's add dp[i][j] and go"

That's how I thought DP was supposed to be.

But recently, I solved a problem... and it broke that pattern completely.

No recursion.

No DP array.

No i, no j, no table.

Still, it felt like Dynamic Programming.

And that's when I paused and asked myself:

“Wait… is this even DP?”

Turned out, it was. Just in disguise.

That's when I realized:

DP isn't just about writing recursion and caching it.

It's more about spotting repeated work and finding smart ways to reuse it.

Mind blown

The Problem

Max of Min for Every Window Size

You're given an array M of length N. For every window size i from 1 to N:

Find all subarrays of size i
Take the minimum of each subarray
From those, find the maximum
Store that in position i of a new array P

Example:

Input: M = [1, 2, 3]

Output: P = [3, 2, 1]

My Brute Force

The moment I read the problem, I felt confident.

"Sliding window + priority queue? Easy!"

I wrote it quickly.

Clean logic. Passed the sample cases.

Hit submit...

and TLE.

That hurt.
That's when I knew…

Maybe it's time to change my thinking.

Flipping the Perspective

Up to this point, I was stuck thinking:

"Fix a window size, slide it, take minimums."

But then I came across a different way of thinking (shoutout to ChatGPT for the nudge):

“What if instead of fixing the window… I fix the element?”

That led to a much better question:

"In how many windows is this element the minimum?"

This flipped everything.

Using a monotonic stack, I found:

left[i]: index of the previous smaller element
right[i]: index of the next smaller element

That gave me the range of window sizes where arr[i] is the minimum.

Now I could directly say:

int len = right[i] - left[i] - 1;
P[len] = max(P[len], arr[i]);

Array:        [10, 20, 30, 50, 10, 70, 30]
Indexes:        0   1   2   3   4   5   6

Fix element:              ↑
                         arr[4] = 10

Find:
   left[4]  = 0   (index of previous smaller)
   right[4] = 7   (index of next smaller)

Window size where arr[4] is min = right - left - 1 = 7 - 0 - 1 = 6

So, 10 is the minimum in all windows of size 6 that include index 4.

What DP Really Means

Dynamic Programming isn't about sticking to recursion or memo tables.

It's just... not doing the same work again and again.

Sometimes it shows up as a clever stack.

Other times, it's a loop with a trick.

And occasionally, it's just thinking from the other side.

I don't know all of it yet, but I've started noticing patterns I never used to.

Maybe that's what DP is not a formula, but a way of noticing.

Some Patterns I Started Noticing

After getting out of the “everything must be recursion” mindset, I started to notice some small things that helped.

Like:

If I keep doing the same thing on subarrays - maybe prefix sum or sliding window is the way.
If I'm checking min or max in ranges a lot - maybe a monotonic stack can save me.
If there are too many nested loops - maybe I can flip how I look at the problem.
And if recursion doesn't even fit - maybe it's just about reusing stuff smartly.

Still figuring it all out, but these small shifts made a big difference for me.

Final Thought

Okay yeah...

So all those “DP = recursion -> memo -> tabulation -> space optimization” steps?

Kinda feels silly now. 😅

This problem made me realize:

DP is just not doing the same thing twice, even if it doesn't look like typical DP.

And honestly?

That realization hit harder than a brute force TLE 💀

I'm still figuring things out, still breaking stuff.

But now I don't reach for recursion every time. I try to think smarter, not just code faster.