2189

2189. Number of Ways to Build House of Cards (Medium)

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:

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 2:

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

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.

 

Constraints:

• 1 <= n <= 500

Companies:
Airbnb

Related Topics:
Math, Dynamic Programming

Similar Questions:

• Champagne Tower (Medium)

Solution 1. Top-down DP

Intuition: Try using 1, 2, 3, ... triangles in the first row, then count how many different houses we can build on top of this first row.

Algorithm:

If we build j houses in the first row, then we can at most build j - 1 houses in the second row.

Let dp[i][j] be the number of different houses we can build given i cards and j houses allowed in the current row.

For dp[i][j], we can try building 1, 2, 3, ..., j houses in the current row.

dp[i][j] = SUM( dp[i - usedCards][housesInCurrentRow - 1] )
                where usedCards = 3 * housesInCurrentRow - 1

The trivial case is dp[0][j] = 1 -- we add one to the answer once we used all the cards.

// OJ: https://leetcode.com/problems/number-of-ways-to-build-house-of-cards/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(N^2)
class Solution {
public:
    int houseOfCards(int n) {
        int m[501][170] = {};
        memset(m, -1, sizeof(m));
        function<int(int, int)> dp = [&](int i, int j) {
            if (i == 0) return 1;
            if (m[i][j] != -1) return m[i][j];
            int h = 1, used = 2, ans = 0;
            for (; h <= j && used <= i; ++h, used += 3) {
                ans += dp(i - used, h - 1);
            }
            return m[i][j] = ans;
        };
        return dp(n, n / 3 + 1);
    }
};

Solution 2. Bottom-up DP

// OJ: https://leetcode.com/problems/number-of-ways-to-build-house-of-cards/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(N)
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];
    }
};