leetcode
leetcode 1201 ~ 1250
建造纸牌屋的方法数

建造纸牌屋的方法数

难度:

标签:

题目描述

代码结果

运行时间: 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`是如何确定的?具体是基于什么考虑?
起始层高`l`的计算方式`3 - n % 3`是为了确保构建每一层至少需要3张卡片的基础上,剩余的卡片数能够被3整除,这样才能保证在接下来的每一层都至少使用3张卡片。因此,`3 - n % 3`是为了找出最小的对3整除的剩余卡片数,从而确定能够开始构建的最低层数。这种方式确保了在给定卡片数量下,可以从最小合理的层高开始构建,同时尽可能高效地利用每张卡片。
🦆
递归函数`dp`中,为什么当`k == 1`时直接返回1?这是否意味着任何剩余卡片数`n`都可以构建出一层?
在递归函数`dp`中,当`k == 1`时直接返回1是因为,如果只剩下一层要建造,那么无论剩下多少张卡片(只要至少为最小层数的卡片数),都只有一种方法来构建这最后一层。`n`在这里代表剩余的卡片数,只要`n`大于等于当前层所需的最小卡片数`lo`,就能构建出这一层。因此,当`k == 1`时意味着在卡片数量允许的情况下,总是有一种方法可以完成最后一层的构建。
🦆
在递归调用中,`lo`的范围是从当前层的`lo`到`n // 2 + 1`,这样的范围设定是基于什么考虑?
在递归调用中,`lo`的范围从当前层的最小卡片数`lo`开始,到`n // 2 + 1`结束,是基于这样的考虑:每一层都应至少比上一层多使用一张卡片,从而保持塔的稳定性和递增的结构特性。范围的上限`n // 2 + 1`确保了在当前层至少留有足够的卡片数供下一层使用。这种设置帮助确保了每一层不仅满足最小卡片数的需求,而且考虑到了剩余卡片数,从而使构建过程中每一层的卡片使用都是合理和可行的。

相关问题