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

## I/ Tóm tắt đề bài
- Hãy đếm số lượng dãy có $n$ phần tử nguyên nhận giá trị từ $1$ đến $m$ và dãy sau khi chạy đoạn code sau sẽ trả về giá trị $k$ ($1 \le k \le n \le 50, 1 \le m \le 100$)

## II/ Lời giải
- Gọi dãy ta cần xây là $A$. Đầu tiên ta có nhận xét, biến `search_cost` tăng khi `maximum_value < arr[i]`, nghĩa là $max(A_1,A_2,...,A_i-1) < A_i$.
- Từ đây, nhìn vào giới hạn đề bài tương đối nhỏ, ta nghĩ ngay đến lời giải quy hoạch động. Trạng thái quy hoạch động là $f(i,j,k)$, nghĩa là số lượng dãy độ dài $i$, mà có giá trị lớn nhất trong dãy là $j$, và có `search_cost` là $k$.
- Chuyển nhãn:
+ Khi đã có trạng thái độ dài $i$, ta sẽ tìm cách chuyển nhãn lên trạng thái độ dài $i+1$ bằng cách thêm một phần tử vào cuối dãy. Khi đó sẽ có hai trường hợp: Giá trị $x$ thêm vào cuối dãy lớn hơn $j$ và ngược lại, giá trị này nhỏ hơn hoặc bằng $j$. Vậy ta có công thức chuyển nhãn khi điền thêm giá trị $x$:
+ Nếu $x \le j$:
$$f(i,j,k) = f(i,j,k) + f(i - 1, j, k)$$
+ Nếu $x > j$:
$$f(i,x,k) = f(i,x,k) + f(i - 1, j, k-1)$$
+ Khi ta điền thêm các giá trị $x \le j$, `search_cost` và giá trị lớn nhất trong dãy không thay đổi.
+ Khi ta điền thêm các giá trị $x > j$, giá trị lớn nhất đổi thành $x$ và `search_cost` tăng thêm $1$.
+ Trạng thái cơ sở là $f(0,0,0)=1$, có duy nhất một dãy độ dài là $0$, chưa có giá trị nào trong dãy nên giá trị lớn nhất vẫn là $0$ và `search_cost` là $0$.

## III/ Nhận xét
- Lời giải trên có độ phức tạp thời gian $O(n \times m^2 \times k)$ và độ phức tạp không gian $O(n \times m \times k)$, tuy vậy vẫn có thể tối ưu thêm.
- Các bài toán dạng đếm số lượng dãy thường sẽ được giải bằng quy hoạch động hoặc tổ hợp. Nhìn vào giới hạn tương đối nhỏ của bài toán, ta có thể đoán được bài toán sử dụng quy hoạch động.