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 :)
Can you give the link to this problem ?
Approach (Recursive DP)
f(i, j) -> minimum cost to divide first i elements into j groups.
f(i, j) = min(f(i + 1, j), f(i + 1, j + 1) + cost[j]) ;