Dp problem

Please explain the following question with an example??


Why should we think of the problem in terms of dp here??

First, we must buy products in order. So, to buy product i, we only need to know where we bought product i-1.
So, the state is a pair (product to buy, last shop used)

Btw, did you check the editorial?

1 Like

For applying dp, think the very basic way: we need two properties to be satisfied here. Optimal Substructure, if we consider buying ith item from jth shop, then the choice of j here can be the one same j from which we bought (i-1)th item or any other. This means solution of problem (i,j) depends on solution of subproblems (i-1,j) or (i-1,shop) where shop denotes any other shop which has minimum cost for selling (i-1)th item. And similarly overlapping property is also satisfied here. Thus, we can apply dp here.

So, for buying i’th item, we have two possibilities. Let us assume that we bought (i-1)th item from from some shop k(1<=k<=m). Then,

  1. If we buy i’th item from the same shop as for the item (i-1), then total cost will be (cost(i-1,k) + discount)
  2. Or what we can do is, dont buy this ith item from the same shop. In this case our cost is (cost(i-1,k)+ price(i,shop) where shop!=k).
  3. We need to have minimum of these two. That will give us the minimum cost for nth item similarly.

Hope this clears…

2 Likes

Thanks… got it