Dp problem

general
1

Please explain the following question with an example??


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

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
3

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
4

Thanks… got it