1420. Build Array Where You Can Find The Maximum Exactly K Comparisons ====================================================================== 题目信息 -------- :题号: 1420 :难度: Hard :主题: 动态规划、计数、前缀最大值 :原题: `LeetCode 1420 `_ :重点: 数组长度为 ``n``、元素范围为 ``[1,m]``;从左扫描时每遇到新的严格最大值,搜索成本增加一,统计成本恰为 ``k`` 的数组 题目重述 -------- 构造长度为 ``n`` 的整数数组,每个元素都位于 ``[1,m]``。从左到右扫描数组,初始最大值为空;每当当前元素严格大于之前所有元素时,搜索成本增加 ``1``。 请统计搜索成本恰好为 ``k`` 的数组数量,并返回结果对 ``10^9 + 7`` 取模后的值。 ``1 <= n, m <= 50``,``1 <= k <= n``。 自建示例 -------- 成本为一表示首元素之后不再出现更大值: .. code-block:: text 输入:n = 2, m = 3, k = 1 输出:6 解释:首元素分别为 1、2、3 时,第二项可选数量为 1、2、3,共六个数组。 数组长度不足以产生指定次数的新最大值时答案为零: .. code-block:: text 输入:n = 1, m = 2, k = 2 输出:0 解释:只有一个元素,搜索成本只能为一。