Day 10 Diving Into Dynamic Programming

Hello Everyone!

I’m Somuya Khandelwal, here to share the updates from Day 5 of Week 2 in my competitive programming journey. Today’s focus was on 1D Dynamic Programming (DP), which is one of the most fascinating techniques I’ve encountered so far. It’s amazing how DP lets you break complex problems into smaller, manageable subproblems, solve them step by step, and combine the solutions efficiently.

---

What I Worked On Today

1. Climbing Stairs (Easy Difficulty)

   • Task: Find the number of ways to climb n stairs if you can take either 1 or 2 steps at a time.
   • Approach:
     • Identified the recurrence relation: dp[i] = dp[i-1] + dp[i-2].
     • Tried both recursive solutions (with memoization) and iterative solutions.
     • Realized that instead of storing all states, I could just keep track of the last two states to optimize space.
   • What I Learned:
     • This problem showed me how to derive the base case and build up the solution iteratively.
     • Space optimization is such a great tool—reducing a DP table to just two variables felt super satisfying.

2. House Robber (Medium Difficulty)

   • Task: Given a row of houses, each with a certain amount of money, find the maximum money you can rob without robbing two adjacent houses.
   • Approach:
     • Formulated the recurrence relation: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
     • Used an iterative approach, where I calculated the optimal solution for each house step by step.
     • Similar to Climbing Stairs, I reduced the space complexity by tracking only the last two states.
   • What I Learned:
     • Balancing choices (to rob or not to rob) at every step made this problem really engaging.
     • It reinforced the importance of thinking about problem constraints when building a solution.

---

What I Learned Today

1. Breaking Problems into Subproblems:

   • Dynamic programming is all about identifying smaller subproblems and solving them incrementally. Both problems today highlighted how subproblem solutions build towards the final answer.

2. Recurrence Relations Matter:

   • Writing a recurrence relation that fits the problem is crucial. It’s the backbone of any DP solution and helps simplify the coding process.

3. Optimize When Possible:

   • Many DP problems, like the ones today, can be optimized to use constant space by storing only what is necessary for the next step.

4. Iterative Solutions for the Win:

   • While recursion is intuitive and works for smaller inputs, iterative solutions are often faster and safer for large inputs since they avoid stack overflow issues.

---

Reflections and Challenges

The House Robber problem was the most interesting challenge for me today. I initially struggled to decide how to handle overlapping subproblems, especially when calculating the maximum money while ensuring no two adjacent houses were robbed. Once I got the recurrence relation right, the rest fell into place. Debugging the edge cases also taught me how crucial it is to think through constraints thoroughly.

Dynamic programming can feel overwhelming at first, but breaking it down into smaller steps makes it manageable. Today’s problems boosted my confidence, and I’m excited to explore more advanced DP concepts soon.

---

Looking Ahead

Week 2 is officially complete, and it’s been such a fulfilling experience! Next week, I’ll start tackling 2D Dynamic Programming, Greedy Algorithms, and Graph Problems. These topics are a step up in complexity, but I’m eager to take on the challenge.

Thank you for following my journey! Stay tuned for more updates as I continue learning, growing, and solving exciting problems in the world of competitive programming.

Best regards,

Somuya