The "Number of Ways to Build House of Cards" problem asks: Given an integer n representing the total number of cards you have, how many distinct ways can you build a house of cards using all the cards, where each "floor" of the house of cards consists of a certain structure:
n cards, and each card can be used only once.
n cards.
For example, if n = 16, you should return the number of distinct ways to build a house of cards using all 16 cards according to the rules above.
At first glance, this problem looks similar to the classic "coin change" or "integer partition" problems, but with a twist: the number of pyramids per floor increases as you go up, and each pyramid requires a fixed number of cards.
A brute-force approach would be to try all combinations of floors and pyramids, but this quickly becomes inefficient for large n. Instead, we need to find a way to systematically generate all possible combinations that use exactly n cards, taking into account the increasing minimum number of pyramids per floor.
The key insight is to view the problem recursively: for each possible number of pyramids on the current floor (starting from the minimum required), subtract the cards used and recursively solve for the remaining cards and the next floor (which requires one more pyramid). Dynamic programming (DP) can help us avoid recomputation.
We solve the problem using recursion with memoization (top-down DP). Here's how:
dp(remaining, minPyramids) be the number of ways to build the house of cards using remaining cards, starting with at least minPyramids pyramids on the current floor.
remaining == 0, we've used all cards in a valid configuration, so return 1. If remaining < 0, this configuration is invalid, so return 0.
k on the current floor (starting from minPyramids), compute the number of cards needed: cards_needed = k * 2 + (k - 1) (2 cards for each pyramid's sides, and 1 card as a connector between each pair of pyramids). For each valid k, recursively call dp(remaining - cards_needed, k + 1).
dp(n, 1) (at least 1 pyramid on the first floor).
This approach ensures we consider all valid ways to build up the house of cards, strictly increasing the minimum number of pyramids per floor as required, and using all cards exactly once.
Let's walk through the algorithm with n = 16:
remaining == 0, count one valid way.
The DP ensures we do not revisit the same (remaining, minPyramids) pairs, efficiently counting all valid configurations.
Brute-force: The naive approach tries all possible combinations of floors and pyramids, leading to an exponential time complexity, roughly O(2^n).
Optimized DP: The DP solution has at most O(n^2) states (since remaining can be from 0 to n and minPyramids from 1 up to about sqrt(n)). Each state does a loop over possible k, but this is bounded by n. Thus, the overall time complexity is O(n^2). Space complexity is also O(n^2) due to memoization.
This problem is a variation of integer partitioning with constraints. By modeling the problem recursively and using memoization, we efficiently count the number of ways to build a house of cards with exactly n cards. The key insights are recognizing the structure of each floor, enforcing the increasing minimum pyramids, and using DP to avoid redundant computation. This approach is both elegant and efficient, transforming a seemingly complex combinatorial problem into a manageable recursive solution.
from functools import lru_cache
class Solution:
def houseOfCards(self, n: int) -> int:
@lru_cache(maxsize=None)
def dp(remaining, min_pyramids):
if remaining == 0:
return 1
if remaining < 0:
return 0
res = 0
k = min_pyramids
while True:
cards_needed = k * 2 + (k - 1)
if cards_needed > remaining:
break
res += dp(remaining - cards_needed, k + 1)
k += 1
return res
return dp(n, 1)
#include <vector>
#include <unordered_map>
class Solution {
public:
std::unordered_map<long long, int> memo;
int houseOfCards(int n) {
return dp(n, 1);
}
int dp(int remaining, int min_pyramids) {
if (remaining == 0) return 1;
if (remaining < 0) return 0;
long long key = ((long long)remaining << 16) | min_pyramids;
if (memo.count(key)) return memo[key];
int res = 0;
for (int k = min_pyramids;; ++k) {
int cards_needed = k * 2 + (k - 1);
if (cards_needed > remaining) break;
res += dp(remaining - cards_needed, k + 1);
}
return memo[key] = res;
}
};
import java.util.*;
class Solution {
Map<String, Integer> memo = new HashMap<>();
public int houseOfCards(int n) {
return dp(n, 1);
}
private int dp(int remaining, int minPyramids) {
if (remaining == 0) return 1;
if (remaining < 0) return 0;
String key = remaining + "," + minPyramids;
if (memo.containsKey(key)) return memo.get(key);
int res = 0;
for (int k = minPyramids; ; ++k) {
int cardsNeeded = k * 2 + (k - 1);
if (cardsNeeded > remaining) break;
res += dp(remaining - cardsNeeded, k + 1);
}
memo.put(key, res);
return res;
}
}
var houseOfCards = function(n) {
const memo = new Map();
function dp(remaining, minPyramids) {
if (remaining === 0) return 1;
if (remaining < 0) return 0;
const key = remaining + ',' + minPyramids;
if (memo.has(key)) return memo.get(key);
let res = 0;
for (let k = minPyramids; ; ++k) {
const cardsNeeded = k * 2 + (k - 1);
if (cardsNeeded > remaining) break;
res += dp(remaining - cardsNeeded, k + 1);
}
memo.set(key, res);
return res;
}
return dp(n, 1);
};