DAY 11 Exploring 1D Dynamic Programming

Hello Everyone!

I’m Somuya Khandelwal, and I’m thrilled to share my progress from Day 1 of Week 3 in my competitive programming journey. Today, I continued my exploration of 1D Dynamic Programming (DP), building on the concepts I practiced last week. The problems I tackled today were challenging but incredibly rewarding, requiring a strong understanding of breaking problems into smaller, manageable states.

---

What I Worked On Today

1. Word Break (Medium Difficulty)

   • Task: Determine if a string can be segmented into a sequence of words from a given dictionary.
   • Approach:
     • I used a DP array where dp[i] indicates whether the substring s[0...i-1] can be formed using the dictionary.
     • For each ending index i, I checked all possible starting points to see if the substring s[j...i-1] was a valid word and dp[j] was true.
   • What I Learned:
     • This problem highlighted how a DP array combined with nested loops can effectively solve segmentation problems.
     • Narrowing the search space by checking only valid word lengths significantly improved efficiency.

2. Coin Change (Medium Difficulty)

   • Task: Find the minimum number of coins needed to make a given amount using an array of denominations.
   • Approach:
     • Created a DP array where dp[i] represents the minimum coins required to make up the amount i.
     • For each coin, iteratively updated the DP array to find the optimal solution for all amounts.
     • Initialized dp[0] = 0 as the base case, representing zero coins needed for an amount of zero.
   • What I Learned:
     • Properly initializing base cases is critical for the DP transitions to work smoothly.
     • Carefully handling cases where the amount cannot be formed is essential to avoid incorrect results.

3. Longest Increasing Subsequence (Medium Difficulty)

   • Task: Find the length of the longest increasing subsequence (LIS) in an array.
   • Approach:
     • Used a DP array where dp[i] stores the length of the LIS ending at index i.
     • For each element, compared it with all previous elements and extended the LIS if the current element was greater.
   • What I Learned:
     • Nested loops work for smaller inputs, but optimizing the solution using techniques like binary search is necessary for larger datasets.
     • Extending subsequences by building on previous valid states was a fun challenge to figure out.

---

Key Takeaways

1. Dynamic Programming Requires Careful State Management:

   • Each problem used a different approach to represent states, whether it was a boolean array (Word Break) or an integer array (Coin Change and LIS).
   • Understanding what the DP array represents and how to transition between states is the foundation of solving DP problems.

2. Base Cases Simplify Transitions:

   • Initializing dp[0] = 0 in Coin Change and dp[i] = 1 in LIS provided a solid starting point for recursive relationships to build upon.

3. Optimization is Key:

   • While brute force solutions work for smaller inputs, optimizing nested loops with techniques like binary search (as in LIS) can drastically improve performance.

4. Iterative Approaches are Robust:

   • Iterative DP solutions avoid recursion’s memory overhead and are generally better suited for large inputs.

---

Reflections and Challenges

The Coin Change problem stood out as the most challenging one today. Managing the transitions in the DP array while ensuring correctness, especially for cases where no solution exists, took me a while to debug. It was a great learning experience, as I had to step back, rethink the logic, and reimplement parts of the solution.

Overall, today’s problems helped me develop a deeper understanding of 1D DP and the importance of clear, structured thinking when breaking down problems into subproblems.

---

Looking Ahead

Tomorrow, I’ll shift gears and work on Math-based problems like Palindrome Number, Plus One, and Factorial Trailing Zeros. These will test my ability to identify patterns and implement efficient calculations.

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

Best,

Somuya