Maximum Coin Collection - Solution & Explanation

Problem Overview: You are given an array of coins. Each position represents the number of coins you can collect from that index. The goal is to compute the maximum coins you can collect while respecting the problem’s selection constraints. A naive greedy pick fails because taking a large value early can block better future combinations.

Approach 1: Brute Force Recursion (Exponential Time, O(2^n) time, O(n) space)

The most direct idea is to explore every possible decision at each index. For each position i, you either collect the coins at that index or skip it. If you collect from i, the constraint prevents taking the immediate neighbor, so the next valid decision moves to i + 2. If you skip, move to i + 1. This creates a binary decision tree that evaluates every valid subset. The recursion depth is O(n), but the number of states grows exponentially, leading to O(2^n) time. This approach helps understand the structure of the problem but quickly becomes impractical for large inputs.

Approach 2: Memoized Search / Top-Down Dynamic Programming (O(n) time, O(n) space)

The recursive structure reveals overlapping subproblems. The maximum coins collectible starting from index i is independent of how you arrived there. Store results in a memo table dp[i] to avoid recomputation. Each state evaluates two choices: take the current coin (coins[i] + dp[i+2]) or skip it (dp[i+1]). Cache the maximum result for each index so every state is computed once. With memoization, the recursion collapses to O(n) time and O(n) space.

This technique is a classic pattern in dynamic programming problems over an array. The key insight is defining a state that represents the best answer from a given index onward and reusing it across recursive calls. The memoized DFS keeps the code clean while achieving optimal performance.

Recommended for interviews: Interviewers typically expect the dynamic programming formulation. Starting with brute force shows you understand the decision tree. Converting it to memoized search demonstrates recognition of overlapping subproblems and the ability to optimize recursion using DP. The top-down solution is both efficient and easy to explain during a whiteboard discussion.