### PROBLEM LINK:

**Author:** nmalviya1929

**Editorialist:** nmalviya1929

### DIFFICULTY:

MEDIUM

### PREREQUISITES:

DP with Bitmasking

### PROBLEM:

We have to buy N different gadgets on N different days buying one gadget each day. Price for buying ith gadget on jth day is (cost of ith gadget on jth day * cost of previous gadget bought on (j-1)th day).

### QUICK EXPLANATION:

We have to maintain previously brought gadget and mask representing all the gadgets brought so far in dp. Current day is not required in dp state as it can be found using number of sets bits in mask.

### EXPLANATION:

Let **P[i][j]** denote price of jth gadget on ith day. We can maintain a mask to represent gadgets brought so far as well as index of gadget brought on previous day.

Now current day will be equal to (number of set bits in mask) +1.

Iterate over all the items not brought so far and call the function recursively.

```
for(int i=0;i<n;i++){
if(((mask>>i)&1)==0)
dp[mask][prev]=min(dp[mask][prev],p[curr][i]*p[curr-1][prev]+func(mask|(1<<i),i));
}
```

Check editorial code for more understanding.

### AUTHORâ€™S AND TESTERâ€™S SOLUTIONS:

Authorâ€™s solution can be found here.