题目大意：
生成数组
给你三个整数 n、m 和 k 。下图描述的算法用于找出正整数数组中最大的元素。
请你生成一个具有下述属性的数组 arr ：
- arr 中有 n 个整数。
- 1 <= arr[i] <= m 其中 (0 <= i < n) 。
- 将上面提到的算法应用于 arr ，search_cost 的值等于 k 。
返回上述条件下生成数组 arr 的 方法数 ，由于答案可能会很大，所以 必须 对 10^9 + 7 取余。
示例 1：
输入：n = 2, m = 3, k = 1 输出：6 解释：可能的数组分别为 [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]
示例 2：
输入：n = 5, m = 2, k = 3 输出：0 解释：没有数组可以满足上述条件
示例 3：
输入：n = 9, m = 1, k = 1 输出：1 解释：可能的数组只有 [1, 1, 1, 1, 1, 1, 1, 1, 1]
示例 4：
输入：n = 50, m = 100, k = 25 输出：34549172 解释：不要忘了对 1000000007 取余
示例 5：
输入：n = 37, m = 17, k = 7 输出：418930126
提示：
1 <= n <= 501 <= m <= 1000 <= k <= n
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1420
解题思路分析：
本周周赛的这4道题目其实都算不上难，可惜我在做Easy题目时竟然错误提交了2次，从而受到10分钟惩罚，导致最终名次只能排到500名左右。
言归正传，看到这种需要对结果进行取模的题目，说明他的结果会很大，这种情况下通常要考虑到使用动态规划DP来解题。熟悉我们套路的朋友都知道，我经常说，动态规划实际上就是带记忆的递归，个人感觉递归思路相对容易理解，因此本题依然使用递归加记忆数组的方式来解题。
首先我们应该明确题目要求的是什么，通过给出的代码我们能清晰理解，代码的含义是从数组首位向后遍历数组中每一个数字，然后找出数组中的最大值，在找最大值过程中，通过维护一个max变量来保存当前最大值，当当前数字大于这个max时，利用当前数字更替这个max。循环结束后，max就是数组中的最大值，同时max被更替的次数就是 search_cost，也是题目给出的k。
解题时，我们建立一个递归函数，
int help(int n, int m, int k, int max)
用语言描述一下这个函数即是，一个长度为n的数组，它的元素是1到m之间的正整数，从头到尾遍历一遍数组，它的search cost为k，当前的最大值为max，返回值为符合这样数组的个数。首先我们要明确一点，如果n是0并且k是0的情况下，那么结果应该返回1，这唯一的一种情况就是一个空数组。这种情况即是递归函数的终止条件。另外如果n或者k出现小于0的情况，说明当前数组不符合条件，应返回0。
递归时，每进一次递归函数，实际上是要为数组当前位置上安排一个数字，该数字可以是1到m之间任意一个，因此我们需要从1循环m来分别模拟出这m种情况，循环中，对于当前选择的数字，如果它大于max，说明我们消耗了一次 search_cost，反之就没有消耗，选择完当前数字后，我们递归到子问题去求解，对于子问题，它的数组长度减一，如果 search_cost 被消耗了一次的话，k值需要减一，反之k不变。另外max等于max(max, 当前选择数字)。m次循环结束后，我们也进行了m次子问题递归，将m个子问题的结果相加即是当前递归的返回结果。
最后别忘记给递归函数加上记忆数组，递归函数的参数中有3个值是会发生改变的，分别是数组长度n，代表search_cost的k，以及当前最大值max。因此我们需要一个3维数组。
如果你完全不懂动态规划的相关知识，或者你没能完全理解递归加记忆数组的解题方法，建议参考这篇文章：LEETCODE常见算法之动态规划DP超详细白话讲解(上)
实现代码：
Integer[][][] memo; // 记忆数组
public int numOfArrays(int n, int m, int k) {
// 初始化记忆数组
memo = new Integer[n+1][k+1][m+1];
// 递归求解
return help(n,m,k,-1);
}
int help(int n, int m, int k, int max){
// 如果数组长度和k都是0，说明当前数组合法，返回1
if(n==0&&k==0) return 1;
// 如果n或者k小于0，当前数组不合法，返回0
if(n<0||k<0) return 0;
// 如果记忆数组中存在当前解，返回记忆数组中的值
if(max!=-1 && memo[n][k][max]!=null) return memo[n][k][max];
// 返回结果
long res=0;
// 循环尝试将当前位置的数字设置为1至m
for(int i=1;i<=m;i++){
// 递归子问题求解
// 将子问题的返回值累加至当前返回值
// 子问题数组长度减一，如果i大于max，k消耗一次，k减一
res+=help(n-1,m,i>max?k-1:k,Math.max(max,i));
}
res %= 1000000007;
if(max!=-1){
memo[n][k][max]=(int)res;
}
return (int)res;
} 本题解法执行时间为62ms。
Runtime: 62 ms, faster than 87.07% of Java online submissions for Build Array Where You Can Find The Maximum Exactly K Comparisons.
Memory Usage: 39.4 MB, less than 100.00% of Java online submissions for Build Array Where You Can Find The Maximum Exactly K Comparisons.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1420-build-array-where-you-can-find-the-maximum-exactly-k-comparisons-解题思路分析/