Leetcode Problem 2189. Number of Ways to Build House of Cards

2189. Number of Ways to Build House of Cards

Leetcode Solutions

Dynamic Programming Approach

  1. Initialize a dynamic programming array dp of size n+1 with all elements set to 0, except dp[0] which is set to 1 (base case: one way to build a house with 0 cards).
  2. Iterate over the number of cards that can form the base of a row, starting from 2 and increasing by 3 each time (i.e., 2, 5, 8, ...), up to n.
  3. For each base size i, iterate backwards through the dp array from n down to i.
  4. For each j in the iteration, update dp[j] by adding dp[j-i] to it. This represents the number of ways to build the remaining structure with j-i cards after using i cards for the current row.
  5. After completing the iterations, return dp[n] which represents the number of ways to build a house of cards using exactly n cards.
UML Thumbnail

Recursive Backtracking Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...