Day 10 Diving Into Dynamic Programming

Hello Everyone!

I am Somuya Khandelwal, here to share the updates from Day 5 of Week 2 of my competitive programming journey. Today’s focus was on 1D Dynamic Programming (DP), one of the most fascinating and powerful techniques for solving optimization problems. DP allows us to break down complex problems into simpler subproblems and solve them efficiently using state-based decision-making.

What I Worked On Today

1. Climbing Stairs (Easy Difficulty)

   • Find the number of distinct ways to climb n stairs, where you can take either 1 or 2 steps at a time.
   • Approach:
     • Derived the recurrence relation dp[i] = dp[i-1] + dp[i-2].
     • Implemented both iterative and recursive solutions with memoization.
   • What I Learned:
     • DP is all about identifying the base case and the recurrence relation.
     • Space optimization is possible by reducing the DP table to two variables.

2. House Robber (Medium Difficulty)

   • Maximize the amount of money you can rob from houses, ensuring you don’t rob two adjacent houses.
   • Approach:
     • Used the recurrence relation dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
     • Implemented an iterative solution for better space efficiency.
   • What I Learned:
     • State-based decision-making is critical for solving optimization problems like this.
     • Understanding the problem constraints helps in designing efficient solutions.

What I Learned Today

1. Identifying Subproblems:

   • Dynamic programming starts with breaking down a problem into smaller, overlapping subproblems.

2. Designing Recurrence Relations:

   • Both Climbing Stairs and House Robber required deriving clear recurrence relations that reflect the problem constraints.

3. Space Optimization:

   • Many DP problems can be optimized to use constant space by storing only the last few states, as seen in Climbing Stairs and House Robber.

4. Iterative vs Recursive Solutions:

   • While recursion with memoization is intuitive, iterative solutions are often more efficient for large inputs due to reduced stack usage.

Reflections and Challenges

The House Robber problem was particularly interesting because it required balancing two choices at every step: robbing the current house or skipping it. Debugging and refining the DP relation took some effort but was ultimately very rewarding.

Dynamic programming challenges often seem daunting at first, but breaking them down into subproblems and identifying patterns simplifies the process. Today’s problems helped me build a strong foundation in 1D DP, setting the stage for tackling more advanced DP problems in the future.

Looking Ahead

With Week 2 complete, I’m excited to plan Week 3, where I’ll explore more advanced topics, including 2D Dynamic Programming, Greedy Algorithms, and Graph Problems. The journey continues, and I can’t wait to tackle new challenges!

Thank you for following along on my journey. Stay tuned for more updates and insights as I continue to grow in the world of competitive programming.