Question

I have been given an array of integers whose length is 0
The cost of Partition is K+no. of duplicate elements in the Array. And If I choose a subarray for Partition then all elements for 1<=i<=j<=n should be present in it i.e, i,i+1,i+2,.....j

Example 1: n=5 , k=1 arr[]={5,1,3,3,3}

So Minimum Cost=3

Optimal Solution should be to consider 3 Partitions {5,1,3}, {3}, {3}. So total cost should be 3*k.

Example 2: n=5, k=14 arr[]={1,4,2,4,4}

So Minimum Cost will be =17.

Optimal Solution should be to Consider the whole array as one partition so cost=k+3 ( since there are three 4's repeated).

Example 3: n=5, k=7 arr[]={3, 5, 4, 5, 1, 3, 4}

Minimum Cost will be: 13

Optimal Solution should be to consider whole as Single Partition since Cost will be K+6. Because Two 3's,4's, and 5's are there + cost of 1 Partition. Therefore 7+6=13. But if we made two Partitions from i=0 to i=2 and i=3 to i=6 so Total_Cost=2*k=14.

So, My Approach towards Question: I used Recursions to Generate all possible Outcomes and choose the minimum one. If my Element was duplicate in the subarray then simply include it into the partition and if it is duplicate then there are two possibilities that I should either include it in the partition thus increasing my cost by 1 or I must create another partition thus increasing my cost by K. Finally I memoized my code...

//Here's my Pseudo Code
int k,n, arr[1009], dp[1009];
int min_cost(int indx, vector &hash)
//My Recursive Function that takes index and hash map as input
{
if(indx>=n) return k;
if(dp[indx]!=-1) return dp[indx]; //Memoization
if(hash[arr[indx]]) //If element is already Present in Hashmap
{
int x=0,y;
//case 1: Include Duplicate in Same Partition

if(hash[arr[indx]]==1) x++; //Just increasing when 1st time any Duplicate Element comes
hash[arr[indx]]++;
x+=(1+min_cost(indx+1,hash)); //Including in Same Partition increasing Cost by 1

//case 2: Create Another Partition

vector hash2(101,0); //Creating new Partition increasing cost by K
hash2[arr[indx]]++;
y=k+min_cost(indx+1,hash2);

return dp[indx]=min(x,y);
}
else //If the element is not Duplicate in Partition
{
hash[arr[indx]]++;
return dp[indx]=min_cost(indx+1,hash);
}
}

Here is one Test Case that is Failing:

n=6, k=2

arr[]={3, 5, 4, 5, 1, 1}

Correct Answer is 4 but mine is giving 6.. please Help !! I found that I made mistake in memoizing my Code. Please Help me memoize my code Correctly so That it gives correct results.

Answer 1

Answer:

What kind of question is this?? So long