I need help with this problem: You are given an array A[] and an array P[] with sizes - N and M. M is always equal to the distinct numbers in A[]. Each value of A[] has a cost assigned in P[]. The cost function for the whole array A[] is : sum for i=2 to i=N (P[A[i]]-P[A[i-1]])^2 (the differences between each 2 elements in a row squared). You can arrange the values in P[] so that this sum of costs is optimal. (each value from 1 to M consists in A[] at least 1 time).
I tried generating all permutations of P[] and then checking, but ofc this is too slow - O(M!*N). I tried thinking of some kind of dynamic programming, but I am still stuck. I think the problem should be solved with dynamic programming or some greedy algorithm. Thanks to anyone who helps. :)