Question: Given an array of N elements We want to divide this into K subarrays ( non-intersecting) such that the total cost is minimum , total cost is sum of cost of all subarrays

Now for a subarray the cost is defined as the no of unordered pairs of elements which have different indices and their values are the same , i.e for array A , i < j && A[i] = A[j]

We want to output the total cost .

Constraints .

2 <= N <= 1e5 .

1 <= A[i] <= N .

2 <= K <= min(N,20) .

Eg : [ 1 , 1 , 2 , 2 , 1 ] and k = 2

Most optimal way is [ 1, 1, 2 ] [2,1] where the cost of subarray one is 1 , subarray 2 is 0

So total cost = 1 + 0 = 1

My Approach .

Seeing the constraints I tried applying a DP of index , k however I was soon faced in a issue where I needed to find the (no.of pairs for a given range l , r) in such a way that it does not exceed the time limit

How to approach such questions

PS : Thank you in advance :)