假设我们有一个值 h 和一个名为 blacklist 的数字列表。我们当前处于高度 h，并且正在玩游戏将小球向下移动到高度 0。现在，在偶数轮（从 0 开始）中，我们可以将球向下移动 1、2 或 4 级台阶。在奇数轮中，我们可以将球向下移动 1、3 或 4 个楼梯。某些级别被列入黑名单。所以如果球到达那里，它会立即死亡。我们必须找到球在高度 0 处可以向下移动的方式数。如果答案太大，则将结果乘以 10^9 + 7。
所以，如果输入像 h = 5 blacklist = [2, 1]，那么输出将是 2，因为在第 0 轮，先移动一步（5 到 4），然后在下一轮从 4 到 0。另一种可能的方法是在第 0 轮，移动两步（5 到 3），然后在下一轮 3 到 0。
让我们看看以下实现以获得更好的理解 -
def solve(h, blacklist): blacklist = set(blacklist) if 0 in blacklist or h in blacklist: return 0 dp = [[0, 0] for i in range(h + 1)] dp[0] = [1, 1] m = 10 ** 9 + 7 for i in range(1, h + 1): for x in [1, 2, 3, 4]: if i - x >= 0 and i - x not in blacklist: if x != 3: dp[i][0] += dp[i - x][1] if x != 2: dp[i][1] += dp[i - x][0] dp[i][0] %= m dp[i][1] %= m return dp[h][0] h = 5 blacklist = [2, 1] print(solve(h, blacklist))
5, [2, 1]输出结果
2