Dynamic Programming Example

Dynamic programming problem explained and solved using C++.

I like programming in general, but the paradigm which appeals to me most is Dynamic programming. Back in 2013, during my college days, I used to  hone my skills by solving problems on CodeChef. But then I got a job and it does not involve a lot of DP.

Recently I've realized that I have become clumsy, and too used to the "safe life", hence I've decided to solve DP problems on HackerEarth, the purpose of this blog is to keep me motivated :p


Samu and Shopping

Samu is in super market and in a mood to do a lot of shopping. She needs to buy shirts, pants and shoes for herself and her family. There are N different shops. Each shop contains all these three items but at different prices. Now Samu has a strategy that she won't buy the same item from the current shop if she had already bought that item from the shop adjacent to the current shop.

Now Samu is confused, because although she want to follow her strategy strictly but at the same time she want to minimize the total money she spends on shopping. Being a good programmer, she asks for your help.

You are provided description about all N shops i.e costs of all three items in each shop. You need to help Samu find minimum money that she needs to spend such that she buys exactly one item from every shop.

Input Format: 
First line contain number of test cases T. Each test case in its first line contain N denoting the number of shops in Super Market. Then each of next N lines contains three space separated integers denoting cost of shirts, pants and shoes in that particular shop.

Output Format:
For each test case, output the minimum cost of shopping taking the mentioned conditions into account in a separate line.

Constraints :
1 ≤ T ≤ 10 
1 ≤ N ≤ 105
Cost of each item (shirt/pant/shoe) does not exceed 104

Sample Input(Plaintext Link)
 1
3
1 50 50
50 50 50
1 50 50
Sample Output(Plaintext Link)
 52
Explanation
There are two ways, each one gives 52 as minimum cost. One way is buy shirt from first shop, pant from second shop and shirt from third shop or she can buy shirt from first shop, shoe from second shop and shirt from third shop.

Both ways , cost comes up to 1 + 50 + 1 = 52

Time Limit: 2 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded if any testcase passes.
Allowed languages: C, CPP, CLOJURE, CSHARP, GO, HASKELL, JAVA, JAVASCRIPT, JAVASCRIPT_NODE, LISP, OBJECTIVEC, PASCAL, PERL, PHP, PYTHON, RUBY, R, RUST, SCALA

Okay, so we have prices of 3 items from n shops. This is best represented as a 2D array/vector with three columns and n rows.

 shirt      pant    shoes

1	50	50
50	50	50
1	50	50

We need to calculate the minimum money required to purchase atleast one item from each shop, so if we buy the cheapest item from each shop we should be fine, BUT we cannot buy the same item from adjacent shops(I wonder why :D). So if we buy shirt from the first shop we have to buy either pant or shoes from the adjacent shop and so on,

Hmm.. looks like a binary tree to me, lets try and represent it as one.

The number(i,j) here denote the indices of the price matrix, where denotes the shop and j  is the item.

We start with -1,-1 as the starting point, because we want the minimum of all the possible selections(Just a way to represent, feel free to change this).

So, if I start with the first item from the first shop, it would be equivalent to choosing the 0th item from the 0th shop in the matrix(think in terms of array indexes), after which I can choose either the Pant(index 1) from the second shop(index 1) OR I could choose shoes(item index 2) from the second shop(index 1), and so on.

These are a lot of combinations, so we will follow a greedy approach. At each node consider that child, which has the least cost. If we follow this approach bottom up,we will arrive at our answer.

If each node(i,j) in the tree represents the cost of buying an item(j) from a shop(i), then it is clear that a lot of things are being recalculated, for ex the nodes(1,0) and (1,2). If we can avoid these recalculation, by remembering the previously calculated values, we can achieve better performance when we have a lot of data, and this is nothing but dynamic programming.

In the code below, we use an array cache[][] to store previously calculated results. We calculate the cost at each node only if it has not been calculated earlier, and store it in the cache for later use.

Here is the code: