Readme

1420.Build-Array-Where-You-Can-Find-The-Maximum-Exactly-K-Comparisons

乍看没有头绪，不妨将题目中的三个变量都作为dp状态变量的下标试一下。第一版本是：dp[i][j][k]表示对于前i个元素、当nums[i]等于j、总共用了k次cost时，总共有多少种方案。

我们试图来转移dp[i][j][k]到前一个状态dp[i-1][?][?]。考虑假设我们在处理第i个元素的时候动用了一次cost，那么意味着前i-1个元素必须都小于j。但是我们的dp设计里并没有这样的信息。dp[i-1][j'][k-1]中的j'表示的仅仅是nums[i]==j'，没有合适的状态来表示前i-1个元素的最大值。

所以我们容易想到并改进得到第二个版本：dp[i][j][k]表示对于前i个元素、最大值等于j、总共用了k次cost时，总共有多少种方案。

同样，考虑假设我们在处理第i个元素的时候新增一次cost，那么意味着nums[i]就是前i个元素的最大值，即是j。于是我们需要前i-1个元素的最大值小于j就可以了。因此有dp[i][j][k] = dp[i-1][j'][k-1]，其中j'=1,2,...,j-1.

考虑假设我们在处理第i个元素的时候没有新增一次cost，那么意味着nums[i]并不是前i个元素的最大值，因此nums[i]的取值可以是1,2,..j. 而对于前i-1个元素的最大值则必须是j。因此有dp[i][j][k] = dp[i-1][j][k]*j.

这里根据加法原理，dp[i][j][k]应该是上面两种情况之和。

最后的答案是dp[n-1][j][k], j=1,2,..m 的总和。