力扣第185场周赛最后一题生成数组,挺有意思的一道题
先来看看题目
题目解析：
首先，此题给出的代码就是一个在数组中寻找最大值的代码
其中的search_cost代表的就是在寻找过程中更新了几次最大值，也就是有多少对相邻的两个数是升序排列的。
再看题目要求，结合刚才的分析，可以把题目抽象成：
要求有多少个有n个整数、整数大小大于1小于m、有k对相邻的两个数是升序排列的数组的数量。
解题思路：
我们可以很快的想到一个暴力解法，枚举所有有n个整数、整数大小大于1小于m的数组，然后利用题目给出的代码检测这些数组的search_cost，为k则答案加1。
此暴力解法复杂度为O(n*(m^n)),这是一个指数级的复杂度，根据题目给出的n，m的范围，那么复杂度可以达到O(50*(100^50)),这个复杂度就是神威太湖之光也算不来。
接下来我们想想有什么办法可以优化，首先分治的思路对于这题肯定是行不通的，因为问题无法无法分割为两个独立的子问题。贪心算法也行不通，因为这个问题是要求一个数量，不是要求一个问题的最优解。
那么还有什么算法适合这个问题呢？
动态规划可行吗？
要判断动态规划是否可行，就要先来看看这个问题是否可以分解为几个重叠的子问题。
记长度为n-1，数组中最大值为m，search_cost为p的数组为A0,这样的数组数量为x0
记长度为n-1，数组中最大值为i(1=
记长度为n，数组中最大值为m，search_cost为p的数组为B，这样的数组数量为y
我们仔细想想，数组A0后面加上任意一个值在[1,m]之间的数是不是就变成了数组B，而数组Ai后面加上任意一个值在[i+1,m]之间的数是不是也变成了数组B。这就对了，数组B就是由数组A0-Am在后面添加一个数演变过来的。所以这道题可以分解为几个重叠子问题，可以用动态规划求解。
那么我们设dp[n][m][p]表示长度为n，数组中最大值为m，search_cost为p的数组数量,可以得到如下的状态转移方程
此算法复杂度O(n*m*k),按照题目给出的范围也就是O(250000),这个复杂度完全可以通过，OK，接下来就是码代码，注意由于结果太大，所以结果要对1000000007取模。
代码
class Solution{public static final int mod = 1000000007;public int numOfArrays(int n, int m, int k){if (m