建造纸牌屋的方法数
难度:
标签:
题目描述
代码结果
运行时间: 155 ms, 内存: 0.0 MB
/*
* Leetcode Problem 2189: Number of Ways to Build House of Cards
*
* Approach:
* 1. Utilize Java Streams to calculate the number of ways to build a house of cards.
* 2. Dynamic programming with streams to store and update results.
* 3. Base case: There is one way to build a house of height 0.
* 4. For each height from 1 to `n`, calculate the number of ways using the results of previous heights.
*/
import java.util.stream.IntStream;
public class Solution {
public int houseOfCards(int n) {
if (n == 0) return 1;
if (n < 0) return 0;
int[] dp = new int[n + 1];
dp[0] = 1;
IntStream.rangeClosed(1, n).forEach(i ->
IntStream.rangeClosed(i, n).forEach(j ->
dp[j] += dp[j - i]
)
);
return dp[n];
}
}
解释
方法:
题解的思路基于递归和动态规划。解题思路中,定义了一个递归函数 dp(k, n, lo),其中 k 代表层级数,n 代表剩余可用的卡片数,lo 为当前层起始最小卡片数。函数的目的是计算能够构建 k 层塔且使用至少 lo 张卡片的方法数。如果当前层使用的卡片数超过剩余卡片数 n,则返回 0。如果仅剩一层 (k == 1),则只有一种构建方式。对于多层情况,递归地计算所有可能的构建方式的总和。外层函数 houseOfCards 求解具体的 n 张卡片可以构建的不同高度的塔的总数,通过迭代每一可能的层高 l,并根据剩余卡片调用 dp 函数。起始层高 l 从 3 - n % 3 开始,到 n 张卡片能支持的最大层数结束,步长为 3。
时间复杂度:
O(k * n^2/2)
空间复杂度:
O(k * n^2/2)
代码细节讲解
🦆
在题解中,起始层高`l`的计算方式`3 - n % 3`是如何确定的?具体是基于什么考虑?
▷🦆
递归函数`dp`中,为什么当`k == 1`时直接返回1?这是否意味着任何剩余卡片数`n`都可以构建出一层?
▷🦆
在递归调用中,`lo`的范围是从当前层的`lo`到`n // 2 + 1`,这样的范围设定是基于什么考虑?
▷