Problem: Number of Ways to Build House of Cards

This problem asks to find the number of distinct ways to build a house of cards using a given number n of cards. A valid house of cards follows specific rules regarding the arrangement of triangles (two cards leaning against each other) and horizontal cards.

Solution Approach: Dynamic Programming (Memoization)

The key observation is that each layer of a house of cards requires 3k + 2 cards, where k is the number of triangles in that layer (and thus the layer index, starting from 0). We can solve this problem using dynamic programming (specifically, memoization) because subproblems (building houses with fewer cards) are reused.

The core function dfs(n, k) recursively determines the number of ways to build a house of cards:

• Base Cases:

  • If 3k + 2 > n, there aren't enough cards to add another layer, so return 0.
  • If 3k + 2 == n, there are exactly enough cards for a single layer, so return 1.

• Recursive Step:

  • Otherwise, explore two options:
    • Add a layer: Recursively call dfs(n - (3k + 2), k + 1) to explore building a house with a new layer (using 3k + 2 cards).
    • Don't add a layer: Recursively call dfs(n, k + 1) to explore building a house without adding another layer (leaving n cards).
  • The total number of ways is the sum of the ways from these two options.

Memoization: To avoid redundant calculations, a memoization table (f in the code) stores the results of dfs(n, k). If a result is already computed, it's retrieved from the table; otherwise, it's computed and stored.

Time and Space Complexity Analysis

• Time Complexity: The memoization table has dimensions approximately n x n/3, leading to a time complexity of O(n²). Each state is visited at most once.
• Space Complexity: The space complexity is also O(n²) due to the memoization table.

Code Implementations

The following code demonstrates the solution in several programming languages:

Python:

class Solution:
    def houseOfCards(self, n: int) -> int:
        @cache
        def dfs(n: int, k: int) -> int:
            x = 3 * k + 2
            if x > n:
                return 0
            if x == n:
                return 1
            return dfs(n - x, k + 1) + dfs(n, k + 1)
 
        return dfs(n, 0)

Java:

class Solution {
    private Integer[][] f;
 
    public int houseOfCards(int n) {
        f = new Integer[n + 1][n / 3 + 1]; //Memoization table
        return dfs(n, 0);
    }
 
    private int dfs(int n, int k) {
        int x = 3 * k + 2;
        if (x > n) return 0;
        if (x == n) return 1;
        if (f[n][k] != null) return f[n][k];
        return f[n][k] = dfs(n - x, k + 1) + dfs(n, k + 1);
    }
}

C++:

class Solution {
public:
    int houseOfCards(int n) {
        vector<vector<int>> f(n + 1, vector<int>(n / 3 + 1, -1)); //Memoization
        function<int(int, int)> dfs = [&](int n, int k) {
            int x = 3 * k + 2;
            if (x > n) return 0;
            if (x == n) return 1;
            if (f[n][k] != -1) return f[n][k];
            return f[n][k] = dfs(n - x, k + 1) + dfs(n, k + 1);
        };
        return dfs(n, 0);
    }
};

Go:

func houseOfCards(n int) int {
    f := make([][]int, n+1)
    for i := range f {
        f[i] = make([]int, n/3+1)
        for j := range f[i] {
            f[i][j] = -1
        }
    }
    var dfs func(n, k int) int
    dfs = func(n, k int) int {
        x := 3*k + 2
        if x > n {
            return 0
        }
        if x == n {
            return 1
        }
        if f[n][k] == -1 {
            f[n][k] = dfs(n-x, k+1) + dfs(n, k+1)
        }
        return f[n][k]
    }
    return dfs(n, 0)
}

TypeScript:

function houseOfCards(n: number): number {
    const f: number[][] = Array(n + 1).fill(null).map(() => Array(Math.floor(n / 3) + 1).fill(-1));
    const dfs = (n: number, k: number): number => {
        const x = 3 * k + 2;
        if (x > n) return 0;
        if (x === n) return 1;
        if (f[n][k] !== -1) return f[n][k];
        return f[n][k] = dfs(n - x, k + 1) + dfs(n, k + 1);
    };
    return dfs(n, 0);
}

These codes all implement the same dynamic programming (memoization) solution, varying only in syntax and specific data structure usage for memoization. They all achieve the same time and space complexity.