Number of Ways to Build House of Cards

 A house of cards is an exciting form of building that involves the use of cards which may be quite interesting and at the same time needs a lot of balance and time and more to do with the construction of the building. In mathematical terms, one can think of looking at the number of different house of card configurations possible given by the number of playing cards.

Problem Description:

You are given an integer n representing the number of playing cards you have. A house of cards meets the following conditions:

• A house of cards consists of one or more rows of triangles and horizontal cards.
• Triangles are created by leaning two cards against each other.
• One card must be placed horizontally between all adjacent triangles in a row.
• Any triangle on a row higher than the first must be placed on a horizontal card from the previous row.
• Each triangle is placed in the leftmost available spot in the row.

Return the number of distinct house of cards you can build using all n cards. Two houses of cards are considered distinct if there exists a row where the two houses contain a different number of cards.

Example 1:

Example 1

Input: n = 2
Output: 1
Explanation: The one valid house of cards is shown.

Example 2:

Example 2

Input: n = 16
Output: 2
Explanation: The two valid houses of cards are shown.
The third house of cards in the diagram is not valid because the rightmost triangle on the top row is not placed on top of a horizontal card.

Example 3:

Example 3

Input: n = 4
Output: 0
Explanation: The three houses of cards in the diagram are not valid.
The first house of cards needs a horizontal card placed between the two triangles.
The second house of cards uses 5 cards.
The third house of cards uses 2 cards.

Solution

Approach 1: Top-down DP

Intuition: Start by using 1, 2, 3, ... triangles in the first row, and then determine how many different houses can be built on top of this initial row.

Algorithm:

Define State Variables:

• Let dp[i][j] represent the number of different houses that can be built with i cards and j houses allowed in the current row.

Row Construction:

• If we build j triangles in the first row, we can build at most j−1 triangles in the second row.
• For each dp[i][j], try building 1, 2, 3, ..., j triangles in the current row.

Transition State:

• dp[i][j]=∑(dp[i−usedCards][j−1])
• where usedCards 3×housesInCurrentRow−1.

Base Case:

• dp[0][j]=1 – this means that we add one to the answer once we have used all the cards.

Detailed Algorithm

• Initialize a 2D array dp where dp[i][j] is initially set to 0 for all i and j.
• Set dp[0][j]=1 for all j because if there are no cards left, there is one way to construct the house.
• Iterate over all possible numbers of cards from 1 to n.
• For each number of cards, iterate over the possible number of houses in the current row.
• Update the dp array based on the number of cards used and the remaining houses.

Code:

Solution 1. Top-down DP

C++

#include <iostream>
#include <functional>
#include <cstring> // For memset
using namespace std;

class Solution {
public:
    int houseOfCards(int n) {
        // Create a memoization table
        int m[501][170];
        // Initialize all values in the memoization table to -1
        memset(m, -1, sizeof(m));

        // Define a lambda function for the DP approach
        std::function<int(int, int)> dp = [&](int i, int j) {
            // Base case: if no cards are left, there is one way to build the house
            if (i == 0) return 1;
            // If this subproblem has been solved, return the stored result
            if (m[i][j] != -1) return m[i][j];
            int h = 1, used = 2, ans = 0;
            // Try building 1, 2, ..., j houses in the current row
            for (; h <= j && used <= i; ++h, used += 3) {
                ans += dp(i - used, h - 1);
            }
            // Store the result in the memoization table and return it
            return m[i][j] = ans;
        };

        // Call the dp function with the initial conditions
        return dp(n, n / 3 + 1);
    }
};

int main() {
    Solution sol;
    
    // Test cases
    int test1 = 16;
    cout << "Number of ways to build a house of cards with " << test1 << " cards: " << sol.houseOfCards(test1) << endl;
    
    int test2 = 10;
    cout << "Number of ways to build a house of cards with " << test2 << " cards: " << sol.houseOfCards(test2) << endl;

    int test3 = 20;
    cout << "Number of ways to build a house of cards with " << test3 << " cards: " << sol.houseOfCards(test3) << endl;
    
    return 0;
}

Output

Number of ways to build a house of cards with 16 cards: 2
Number of ways to build a house of cards with 10 cards: 1
Number of ways to build a house of cards with 20 cards: 1

Solution 2. Bottom-up DP

C++

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int houseOfCards(int n) {
        vector<int> dp(n + 1);
        dp[0] = 1;
        for (int h = 1; h <= n / 3 + 1; ++h) { // build `h` houses in the current row
            int used = 3 * h - 1; // cards used in the current row
            for (int i = n; i >= used; --i) { // the # of cards available to build houses in the current row and rows above.
                dp[i] += dp[i - used];
            }
        }
        return dp[n];
    }
};

int main() {
    Solution sol;
    
    // Test cases
    int test1 = 16;
    cout << "Number of ways to build a house of cards with " << test1 << " cards: " << sol.houseOfCards(test1) << endl;
    
    int test2 = 10;
    cout << "Number of ways to build a house of cards with " << test2 << " cards: " << sol.houseOfCards(test2) << endl;

    int test3 = 20;
    cout << "Number of ways to build a house of cards with " << test3 << " cards: " << sol.houseOfCards(test3) << endl;
    
  
    return 0;
}

Output

Number of ways to build a house of cards with 16 cards: 2
Number of ways to build a house of cards with 10 cards: 1
Number of ways to build a house of cards with 20 cards: 1

Conclusion

This approach efficiently counts the number of distinct ways to build a house of cards using dynamic programming. By iterating over possible rows and using previously computed results, it ensures that all configurations are explored while keeping the computation manageable. The base case and state transitions are designed to capture all valid house configurations according to the problem constraints.