Skip to main content

What Can ONE Element Do?

Decision Framework

If local choices lead to global solution → GREEDY

If choices depend on future outcomes → DYNAMIC PROGRAMMING

If you can split into independent subproblems → DIVIDE & CONQUER

Understanding "Choices Depend on Future Outcomes"​

THE DP PARADOX RESOLVED

You might wonder: "If choices depend on future outcomes, doesn't that mean the future affects the past?"

Not quite! Here's the subtle but crucial distinction:

What "Choices depend on future outcomes" ACTUALLY means:

  • When making a decision NOW, you must consider what will happen LATER
  • You can't be greedy (picking locally optimal without thinking ahead)
  • This is why we need DP instead of greedy algorithms

What it does NOT mean:

  • That your history affects your future options
  • That different paths to the same state lead to different futures

The Key Insight:

  • When SOLVING: We think about future consequences (this is why it's DP, not greedy)
  • When STORING: We only remember the best result at each state, not the history (optimal substructure)

Example: Minimum Path Sum

  • ❌ GREEDY: "Pick the smallest neighbor" (ignores future consequences)
  • ✅ DP: "Consider both neighbors and pick based on their optimal future paths"
  • ✅ OPTIMAL SUBSTRUCTURE: "At cell (2,3) with sum 42, the future is the same regardless of how I got here"

The Resolution:

  • The past doesn't constrain your future options (optimal substructure)
  • But understanding the future helps you make better present decisions (why it's DP)

In other words:

  • Your history is forgotten (we only track the best state value)
  • But future consequences are anticipated (we solve subproblems to inform current choices)

This is the essence of Dynamic Programming!

📖 See this paradox in action: Minimum Path Sum - The Paradox Section