Number of Ways to Build House of Cards - Video Solutions

Problem Overview: You are given n cards and must count how many distinct houses of cards you can build. Each level contains k card triangles and requires exactly 3k - 1 cards. Higher levels must use strictly fewer triangles than the level directly below.

The challenge is deciding how many triangles to place on each level while keeping the total number of cards ≤ n and maintaining the strictly decreasing structure.

Approach 1: Brute Force Recursive Search (Exponential Time, O(n) Space)

Try every possible number of triangles k for the current level. Each choice consumes 3k - 1 cards and recursively attempts to build the next level using fewer triangles. This explores all valid sequences of decreasing triangle counts. The approach is simple but inefficient because the same states (remaining cards and previous triangle limit) are recomputed many times. Time complexity grows exponentially with n, while recursion depth uses O(n) space in the worst case.

Approach 2: Memoization Search (Top-Down Dynamic Programming) (O(n²) Time, O(n²) Space)

Cache results for states defined by (remainingCards, prevTriangles). From a given state, iterate over possible triangle counts k where k < prevTriangles and 3k - 1 ≤ remainingCards. For each valid k, recursively compute ways to build the rest of the structure using remainingCards - (3k - 1). Memoization ensures each state is solved once, eliminating repeated work. This transforms the exponential recursion into a manageable dynamic programming solution with roughly O(n²) time and space complexity. The approach relies on recursion plus caching, a common technique in dynamic programming problems.

Approach 3: Bottom-Up Dynamic Programming (O(n²) Time, O(n) Space)

The same recurrence can be built iteratively. Treat each possible level size as a "group" with cost 3k - 1. Build a DP array where dp[c] represents the number of ways to use exactly c cards. Iterate through valid level sizes and update states while enforcing the strictly decreasing triangle constraint. This formulation avoids recursion and often reduces memory usage. The logic still depends on counting combinations of valid level sizes derived from the mathematical rule 3k - 1, making it a mix of math reasoning and dynamic programming.

Recommended for interviews: The memoized top-down DP is the most practical explanation during interviews. Start with the recursive idea to show understanding of the structure, then add caching to remove duplicate work. Interviewers expect you to recognize overlapping subproblems and convert the recursion into dynamic programming.