DAY 23 Dynamic Programming: Turning Complexity Into Simplicity

Hey Everyone!

Today was all about Dynamic Programming (DP)—a technique that turns daunting challenges into manageable subproblems. DP always feels like solving a series of mini-puzzles that come together to create a big picture. The key is finding the right recurrence relation and using it as a guide, like a compass navigating through a dense forest of complexity.

---

How the Day Played Out

1. Climbing Stairs (Easy Difficulty)

   • Task: Determine the number of distinct ways to climb n stairs, where you can take either 1 or 2 steps at a time.
   • The Strategy:
     • Created a DP array where dp[i] represented the number of ways to reach the ith step.
     • Used the recurrence relation dp[i] = dp[i-1] + dp[i-2] to build the solution iteratively.
   • The Fun Part:
     • Recognizing the Fibonacci-like nature of this problem was satisfying—it’s always rewarding to spot patterns that simplify problem-solving.

2. Longest Increasing Subsequence (Medium Difficulty)

   • Task: Find the length of the longest increasing subsequence in an array.
   • The Strategy:
     • Used a DP array where dp[i] tracked the length of the LIS ending at index i.
     • Updated dp[i] by comparing it with all previous indices to see if the current number could extend a subsequence.
   • The Fun Part:
     • Watching the array evolve and seeing the subsequences form dynamically felt like solving a puzzle that shifted with every iteration.

3. Partition Equal Subset Sum (Medium Difficulty)

   • Task: Determine if an array can be partitioned into two subsets with equal sums.
   • The Strategy:
     • Treated the problem as a 0/1 Knapsack problem, checking if a subset with a sum equal to totalSum / 2 could be formed.
     • Used a DP table to track all possible subset sums using the array elements.
   • The Fun Part:
     • Realizing how a subset-sum problem connects to knapsack concepts felt like uncovering hidden links between seemingly unrelated ideas.

---

What Made Today Special

1. Spotting Patterns Everywhere:

   • From Fibonacci-like sequences in Climbing Stairs to the dynamic chain-building in Longest Increasing Subsequence, today was all about discovering and leveraging patterns.

2. Building Solutions Step by Step:

   • DP emphasizes solving smaller subproblems first, which feels like laying the foundation for a larger, more intricate structure.

3. Finding Hidden Connections:

   • Turning Partition Equal Subset Sum into a knapsack problem was a highlight—it showed how concepts from one domain can elegantly solve problems in another.

---

Key Takeaways

• The Recurrence Relation is Key:

  • A clear recurrence relation acts as the backbone of any DP solution, providing structure and direction for the problem-solving process.

• Space Optimization Matters:

  • Problems like Climbing Stairs can be optimized to use constant space by keeping track of only the last two states instead of a full DP array.

• Think Like a Storyteller:

  • Every DP problem is like a story where each subproblem represents a chapter, and solving them sequentially leads to the final resolution.

---

Reflections

The Partition Equal Subset Sum problem stood out as the most intriguing challenge today. It required deep thinking and creativity to transform it into a knapsack problem, which felt like finding a key to unlock a hidden door. Meanwhile, Longest Increasing Subsequence was a rewarding exercise in managing dependencies and tracking dynamic updates—watching the subsequences take shape was particularly satisfying.

---

What’s Next?

Tomorrow, I’ll be diving into Graph Problems, tackling challenges like Number of Islands, Course Schedule, and Shortest Path in Binary Matrix. These problems will test my ability to traverse and manipulate graphs while solving real-world-inspired challenges.

Thank you for joining me on this exciting journey! Let’s keep exploring and growing together as we tackle more competitive programming adventures.

Best regards,

Somuya