Build Array Where You Can Find The Maximum Exactly K Comparisons

This approach uses bottom-up dynamic programming. We define a 3D DP state dp[i][j][l] representing the number of ways to build an array of length i with a maximum value of exactly j and a search cost of l. The key to improving efficiency over the naive DP is to optimize the transition. The transition requires summing up values from the previous state, which can be done efficiently using a prefix sum technique, reducing the complexity of each state calculation from O(m) to O(1).

• Initialize a 3D DP table dp[n+1][m+1][k+1].
• Set base cases: dp[1][j][1] = 1 for j from 1 to m.
• Iterate i from 2 to n (length of array).
• Iterate l from 1 to k (cost).
• Initialize prefixSum = 0.
• Iterate j from 1 to m (max value).
  • Calculate dp[i][j][l] = (dp[i-1][j][l] * j + prefixSum) % MOD.
  • Update prefixSum = (prefixSum + dp[i-1][j][l-1]) % MOD.
• Sum up dp[n][j][k] for all j from 1 to m to get the final answer.

Let dp[i][j][l] be the number of ways to construct an array of length i such that its maximum element is j and the search cost is l. Our goal is to compute sum(dp[n][j][k]) for all j from 1 to m.

Base Case: For an array of length 1, arr = [j], the maximum is j and the cost is 1. So, dp[1][j][1] = 1 for 1 <= j <= m.

Recurrence Relation: To compute dp[i][j][l], we consider how the i-th element is added to an array of length i-1.

• Case 1: The i-th element is not a new maximum. This means the maximum of the first i-1 elements was already j, and the i-th element is chosen from 1, ..., j. There are j choices for the i-th element. The number of ways is dp[i-1][j][l] * j.
• Case 2: The i-th element is a new maximum, and its value is j. This means the maximum of the first i-1 elements was some value p < j, and the cost for the prefix was l-1. The number of ways is the sum of dp[i-1][p][l-1] for all p from 1 to j-1.

The full recurrence is: dp[i][j][l] = (dp[i-1][j][l] * j) + (sum_{p=1}^{j-1} dp[i-1][p][l-1]).

Optimization: The summation term sum_{p=1}^{j-1} dp[i-1][p][l-1] is a prefix sum. As we iterate j from 1 to m (for fixed i and l), we can maintain this sum in a variable, updating it in O(1) at each step.

class Solution {
    public int numOfArrays(int n, int m, int k) {
        if (k == 0) return 0;
        int MOD = 1_000_000_007;
        long[][][] dp = new long[n + 1][m + 1][k + 1];

        // Base case: for length 1, any max j in [1, m] has cost 1.
        for (int j = 1; j <= m; j++) {
            dp[1][j][1] = 1;
        }

        for (int i = 2; i <= n; i++) {
            for (int l = 1; l <= k; l++) {
                long prefixSum = 0;
                for (int j = 1; j <= m; j++) {
                    // Case 1: The i-th element is not a new maximum.
                    long ways = (dp[i - 1][j][l] * j) % MOD;
                    
                    // Case 2: The i-th element is a new maximum, j.
                    // The prefix sum is sum_{p=1}^{j-1} dp[i-1][p][l-1].
                    ways = (ways + prefixSum) % MOD;
                    
                    dp[i][j][l] = ways;

                    // Update prefix sum for the next iteration of j.
                    prefixSum = (prefixSum + dp[i - 1][j][l - 1]) % MOD;
                }
            }
        }

        long ans = 0;
        for (int j = 1; j <= m; j++) {
            ans = (ans + dp[n][j][k]) % MOD;
        }
        return (int)ans;
    }
}