golang 解法, 执行用时: 0 ms, 内存消耗: 6.5 MB, 提交时间: 2023-10-21 23:25:28

func houseOfCards(n int) int {
	dp:= make([]int, n + 1)
	dp[0] = 1
	ans := 0
	for i := 1; (i * (3*i + 1)) / 2 <= n; i++ {
		dp1:= make([]int, n + 1)
		for  j := 3*i - 1; j <= n; j++ {
			if j - 3 * i >= 0 {
				dp1[j] += dp1[j - 3*i]
			}
			dp1[j] += dp[j - (3*i - 1)]
		}
		dp = dp1
		ans += dp[n]
	}
	return ans
}

java 解法, 执行用时: 5 ms, 内存消耗: 38.6 MB, 提交时间: 2023-10-21 23:25:15

class Solution {
    public int houseOfCards(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int num = 2; num <= n; num += 3) {
            for (int j = n; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        return dp[n];
    }
}

python3 解法, 执行用时: 3580 ms, 内存消耗: 269.5 MB, 提交时间: 2023-10-21 23:24:51

# 1 <= n <= 500
from functools import lru_cache, cache

class Solution:
    def houseOfCards(self, n: int) -> int:
        @lru_cache(None)
        def dfs(curTriangle: int, remain: int) -> int:
            if remain <= 0:
                return int(remain == 0)
            res = 0
            for nextTriangle in range(curTriangle):
                res += dfs(nextTriangle, remain - 2 * nextTriangle - (nextTriangle - 1))
            return res

        res = 0
        for baseTriangle in range(1, n):
            res += dfs(baseTriangle, n - 2 * baseTriangle - (baseTriangle - 1))
        return res
        

    def houseOfCards2(self, n: int) -> int:
        @cache
        def dp(k, n, lo):
            if lo > n: return 0
            if k == 1: return 1
            return sum(dp(k - 1, n - lo, lo + 1) for lo in range(lo, n // 2 + 1))
        return sum(dp(l, (n - 2 * l) // 3, 0) for l in range(3 - n % 3, round(sqrt(2 * n / 3 + 1 / 36) - 1 / 6) + 1, 3))

cpp 解法, 执行用时: 12 ms, 内存消耗: 12 MB, 提交时间: 2023-10-21 23:23:15

class Solution {
public:
    int houseOfCards(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        int res = 0;
        // minn = 堆叠 i 行所需的最少总木棒数
        // 下面用了滚动数组的方式求解
        for(int i = 1; (i * (3*i + 1)) / 2 <= n; ++i) {
            vector<int> ndp(n + 1, 0);
            for(int j = 3*i - 1; j <= n; ++j) {
                if(j - 3 * i >= 0) {
                    ndp[j] += ndp[j - 3*i];
                }
                ndp[j] += dp[j - (3*i - 1)];
            }
            dp.swap(ndp);
            res += dp[n];
        }
        return res;
    }
};