DAY 11 Exploring 1D Dynamic Programming

Hello Everyone!

I am Somuya Khandelwal, and I’m excited to share my progress from Day 1 of Week 3 in my competitive programming journey. Today’s focus was on 1D Dynamic Programming (DP), which is a continuation of the concepts I practiced in Week 2. The problems today were challenging yet rewarding, as they required a solid understanding of state-based decision-making and optimization techniques.

What I Worked On Today

1. Word Break (Medium Difficulty)

   • Given a string and a dictionary of words, determine if the string can be segmented into a space-separated sequence of dictionary words.
   • Approach:
     • Used a boolean DP array where dp[i] indicates if the substring s[0...i-1] can be segmented.
     • Iteratively checked for each possible word ending at i if the previous segment was valid.
   • What I Learned:
     • The combination of a DP array and nested loops is effective for solving segmentation problems.
     • Optimized checks by iterating only over valid word lengths.

2. Coin Change (Medium Difficulty)

   • Determine the minimum number of coins required to make up a given amount.
   • Approach:
     • Used a DP array where dp[i] represents the minimum number of coins needed to make the amount i.
     • For each coin, updated the DP array to find the optimal solution for all amounts.
   • What I Learned:
     • DP problems often require initializing base cases (e.g., dp[0] = 0) for proper state transitions.
     • Iterating over coins efficiently handles the subproblems for all amounts.

3. Longest Increasing Subsequence (Medium Difficulty)

   • Find the length of the longest increasing subsequence in an array.
   • Approach:
     • Used a DP array where dp[i] stores the length of the LIS ending at index i.
     • Updated each dp[i] by comparing it with all previous indices and extending valid subsequences.
   • What I Learned:
     • Nested loops can be used to compare elements, but optimizations (e.g., binary search) can significantly reduce time complexity.
     • Transition logic is key: extending an LIS depends on previous valid states.

What I Learned Today

1. Dynamic Programming State Representation:

   • Each problem had a unique way of representing states, whether through boolean arrays (Word Break) or integer arrays (Coin Change and LIS).

2. Base Cases and Initialization:

   • Properly initializing base cases simplifies transitions in DP solutions. For example, dp[0] = 0 in Coin Change and dp[i] = 1 in LIS.

3. Optimization Opportunities:

   • While all problems today were solved using DP arrays, advanced optimizations (e.g., binary search for LIS) can further improve performance for larger inputs.

4. Iterative vs Recursive Solutions:

   • Iterative DP solutions avoid the overhead of recursion and are more memory-efficient, making them ideal for competitive programming.

Reflections and Challenges

The Coin Change problem was the most challenging, as it required carefully managing transitions and handling cases where a solution might not exist (e.g., when the amount cannot be formed with the given coins). Debugging the DP array transitions took time but helped me understand the importance of clear logic.

Overall, today’s problems strengthened my confidence in 1D DP and prepared me for more complex challenges in the coming days.

Looking Ahead

Tomorrow, I’ll shift focus to Math-based problems, tackling challenges like Palindrome Number, Plus One, and Factorial Trailing Zeros. These problems will test my understanding of mathematical patterns and efficient computations.

Thank you for following my journey! Stay tuned for more updates as I continue to explore the fascinating world of competitive programming.