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。

自建示例

成本为一表示首元素之后不再出现更大值:

输入:n = 2, m = 3, k = 1
输出:6
解释:首元素分别为 1、2、3 时,第二项可选数量为 1、2、3,共六个数组。

数组长度不足以产生指定次数的新最大值时答案为零:

输入:n = 1, m = 2, k = 2
输出:0
解释:只有一个元素,搜索成本只能为一。