难度: Medium
Submission
运行时间: 155 ms
内存: 0.0 MB
@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))
class Solution:
def houseOfCards(self, n: int) -> int:
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))
Explain
题解的思路基于递归和动态规划。解题思路中，定义了一个递归函数 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)
from functools import cache
import math
class Solution:
@cache
def dp(self, k, n, lo):
# 如果当前层使用的卡片数超过剩余卡片数，返回 0
if lo > n: return 0
# 如果只剩下一层，返回 1 种方法
if k == 1: return 1
# 计算所有可能的构建方式的总和
return sum(self.dp(k - 1, n - lo, lo + 1) for lo in range(lo, n // 2 + 1))
def houseOfCards(self, n: int) -> int:
# 计算可以构建的不同高度的塔的总数
return sum(self.dp(l, (n - 2 * l) // 3, 0) for l in range(3 - n % 3, round(math.sqrt(2 * n / 3 + 1 / 36) - 1 / 6) + 1, 3))
Explore
起始层高`l`的计算方式`3 - n % 3`是为了确保构建每一层至少需要3张卡片的基础上，剩余的卡片数能够被3整除，这样才能保证在接下来的每一层都至少使用3张卡片。因此，`3 - n % 3`是为了找出最小的对3整除的剩余卡片数，从而确定能够开始构建的最低层数。这种方式确保了在给定卡片数量下，可以从最小合理的层高开始构建，同时尽可能高效地利用每张卡片。
在递归函数`dp`中，当`k == 1`时直接返回1是因为，如果只剩下一层要建造，那么无论剩下多少张卡片（只要至少为最小层数的卡片数），都只有一种方法来构建这最后一层。`n`在这里代表剩余的卡片数，只要`n`大于等于当前层所需的最小卡片数`lo`，就能构建出这一层。因此，当`k == 1`时意味着在卡片数量允许的情况下，总是有一种方法可以完成最后一层的构建。
在递归调用中，`lo`的范围从当前层的最小卡片数`lo`开始，到`n // 2 + 1`结束，是基于这样的考虑：每一层都应至少比上一层多使用一张卡片，从而保持塔的稳定性和递增的结构特性。范围的上限`n // 2 + 1`确保了在当前层至少留有足够的卡片数供下一层使用。这种设置帮助确保了每一层不仅满足最小卡片数的需求，而且考虑到了剩余卡片数，从而使构建过程中每一层的卡片使用都是合理和可行的。