606画作

问题描述

在一个充满色彩的艺术画廊里，小艾拥有 n 幅长度不一的画作，每幅画的长度都是从 1 到 n 的自然数。小艾的目标是将这些画作以特定的顺序摆放，并确保从入口处可以清晰地恰好看到 k 幅画作。判断某幅画是否可见的标准是：它左侧的画作中没有比它更高的遮挡物。

小艾想要计算出所有可能的摆放方式，以满足上述可见性条件。由于结果可能会非常庞大，需要将最终的答案对 10^9 + 7 进行取模后输出。

约束条件：

• 时间限制：3 秒
• 数据范围为 1 ≤ k ≤ n ≤ 3000

解题思路

这道题目可以通过动态规划来解决。定义 dp[i][j] 表示前 i 幅画中恰好有 j 幅画可见的排列数。对于每一幅画，我们有两种选择：

1. 当前画作是最高的：此时它一定是可见的，因此 dp[i][j] += dp[i-1][j-1]。
2. 当前画作不是最高的：这样它不会被看到，除了最高的还有 i 种选择来保持不是最高的状态，因此 dp[i][j] += dp[i-1][j] * i。

为了优化空间复杂度，可以使用滚动数组，仅保留前一状态和当前状态。

代码实现

from typing import List

mod = int(1e9 + 7)
def solution(n: int, k: int) -> int:
    pre = [0] * (k + 1)
    pre[0] = 1
    for i in range(n):
        cur = [0] * (k + 1)
        for j in range(1, k + 1):
            cur[j] = (pre[j - 1] + i * pre[j]) % mod
        pre = cur.copy()
    return pre[k]

if __name__ == '__main__':
    print(solution(n=4, k=2) == 11)
    print(solution(n=6, k=3) == 225)
    print(solution(n=7, k=4) == 735)
    print(solution(n=9, k=5) == 22449)