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

• 결국 못풀었던 문제. 아래와 같은 방식으로 접근했는데 실패했다.
• (index, maxValue, cost)를 상태 State로 정의하고 (0, 0, 0) 부터 시작하여 다음 상태를 구한다.
• (0, 0, 0)에 대한 경우의 수는 1로 한다.
• 다음 상태는 현재 상태에서 index + 1 을 하고 2가지 경우로 나누어 처리한다.
• maxValue가 동일하면 cost가 그대로인 것이므로 기존 경우의 수에 maxValue 만큼을 곱한다.
• 최대 값을 maxValue + 1 ~ m까지 바꿔가면서 각각의 경우의 수에 기존 경우의 수를 넣는다.

• DP에서는 기존 상태 값들로부터 새로운 상태값을 만들어내는 방식으로 접근하는 것이 필요하다.
• 먼저 array의 첫번째 element는 1부터 m까지 선택 가능하고 이때 경우의 수는 1이 된다. 따라서 d[1][i][1] = 1 (i = 1, 2, ..., m) 이다.
• 그 다음 두번째 element 부터 n 번째 element까지 경우의 수를 계산하면 된다.
• 각 element에 대해서 maxValue가 1 ~ m인 경우, cost가 1 ~ k 인 경우에 따라 경우의 수를 계산한다.
• d[len][maxValue][cost] 값을 순서대로 계산한다.
• 여기서 경우의 수는 이전 경우의 수로 부터 구할 수 있는데 cost가 이전에 비해서 증가한 경우와 그렇지 않은 경우를 구분해서 더하면 된다.
• cost가 증가한 경우
• cost가 증가하기 전의 상태는 d[len - 1][i][cost - 1] 에 해당된다.
• cost가 증가했다는 것은 이전 maxValue 값이 현재보다 작다는 의미이다. 따라서 (i = 1 ~ maxValue - 1) 이다.
• 해당되는 값을 모두 더해주면 된다.
• cost가 그대로인 경우
• cost가 그대로라면 maxValue의 이전, 현재 값이 동일하다는 의미이다. 그렇다면 array element의 현재 값은 1 ~ maxValue 중에서 고를 수 있으므로 경우의 수는 maxValue가 된다. 이를 이전 경우의 수와 곱해야 하므로 결과값에 d[len - 1][maxValue][cost] * maxValue를 더해주면 된다.
• 최종 결과는 길이가 n, cost가 k인 모든 경우의 수를 더해주면 된다.
• d[n][i][k] (i = 1 ~ m) 값을 모두 더한다.

static constexpr long long MOD_BASE = 1e9 + 7;
class Solution {
public:
    int numOfArrays(int n, int m, int k) {
        vector<vector<vector<long long>>> d(n + 1, vector<vector<long long>>(m + 1, vector<long long>(k + 1, 0)));

        for (int i = 1; i <= m; ++i) {
            d[1][i][1] = 1;
        }
        for (int len = 2; len <= n; ++len) {
            for (int maxValue = 1; maxValue <= m; ++maxValue) {
                for (int cost = 1; cost <= k; ++cost) {
                    long long sum = 0;
                    for (int i = 1; i < maxValue; ++i) {
                        sum = (sum + d[len - 1][i][cost - 1]) % MOD_BASE;
                    }
                    d[len][maxValue][cost] = (d[len - 1][maxValue][cost] * maxValue + sum) % MOD_BASE;
                }
            }
        }
        long long result = 0;
        for (int i = 1; i <= m; ++i) {
            result = (result + d[n][i][k]) % MOD_BASE;
        }
        return result;
    }
};