Daily 27/01/2024: [629. K Inverse Pairs Array](https://leetcode.com/problems/sum-of-subarray-minimums/)

# 1. Tóm tắt đề bài
Cho một mảng số nguyên ```nums```, một cặp nghịch đảo là một cặp số nguyên ```[i, j]``` trong đó ```0 <= i < j < nums.length``` và ```nums[i] > nums[j]```.

Cho hai số nguyên ```n``` và ```k```, trả về số mảng khác nhau gồm các số từ ```1``` đến ```n``` sao cho có đúng ```k``` các cặp nghịch đảo.

Trả về kết quả theo modulo $10^9 + 7$

#### Giới hạn
- $1 \le$ ```n``` $\le 1000$
- $0 \le$ ```k``` $\le 1000$

# 2. Tóm tắt lời giải

#### Phân tích
- Trước hết có một nhận xét nếu ta thêm một số n vào dãy mà n lớn nhất ví dụ là 4 mà trước đó đã xét 1, 2, 3 thì ta có thêm các cách tạo nghịch đảo sau:
- 4xxx: tạo 3 nghịch đảo
- x4xx: tạo 2 nghịch đảo
- xx4x: tạo 1 nghịch đảo
- xxx4: tạo 0 nghịch đảo
- Rõ ràng ta có thể suy ra được bài toán quy hoạch động với
- ```dp[n][k]```: với k là số cặp ngịch đảo được tạo với n số.
- ```dp[n][k] = dp[n - 1][k - 0] + dp[n - 1][k - 1] + ... + dp[n - 1][k - (n - 1)]``` **(!)**
- Lý giải tại sao lại là ```k - (n - 1)``` thì chúng ta chỉ có thể tạo thêm nhiều nhất ```n - 1``` nghịch đảo khi nhét ```n``` đứng đầu như ở ví dụ trên.
- Với công thức ở trên các bạn đọc có thể thực hiện quy hoạch động với độ phức tạp $O(n^3)$. Và tối ưu vòng lặp cuối sử dụng kĩ thuật prefix sum thành $O(n^2)$.
- Một cách khác đơn giản hơn là chúng ta sử dụng tìm công thức đệ quy của dp.
- Thật vậy:
- ```dp[n][k - 1] = d[n - 1][k - 1] + dp[n - 1][k - 2] + ... + dp[n - 1][k - n]``` **(*)**
- Trừ **(!)(*)** ta sẽ được: ```dp[n][k] = dp[n][k - 1] + dp[n - 1][k] - dp[n - 1][k - n]```.
- Bài toán từ đây có thể sử dụng công thức $O(n^2)$.

# 3. Lời giải chi tiết
- Các bạn triển khai theo công thức quy hoạch động trên.
- Các bạn chú ý trường học cơ sở là ```k == 0``` thì chỉ duy nhất có 1 cách xếp với bất kì ```n```.

#### Code
- Ở đây code rất đặc biệt (trông rất mất nết) vì không dùng mảng để lưu bộ nhớ mà lại đệ quy thuần. Rất đơn giản vì python khá tiện lợi vì có cache lưu lại rất cả giá trị hàm đã gọi. Mình vừa tìm thấy vì mình hay đi mò code tìm trick python :))

from functools import cache

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        @cache
        def dp(n, k):
            if k == 0: return 1
            if n == 1 or k < 0: return 0
            return dp(n, k-1) + dp(n-1, k) - dp(n-1, k-n)
        return dp(n, k) % (10**9+7)

#### Độ phức tạp
$O(n^2)$
# 4. Kết luận & gợi ý mở rộng
- Bài này luyện tập khá tốt về tính vận dụng toán học trong công thức quy hoạch động.
> Hãy dùng nghị lực và sự kiên trì để đánh bại mọi thứ.

###### #Hashtag: <span style='color: blue'>Hash Map</span>