Dynamic programming problems can be difficult to solve as a beginner.Today's blog will tour us through the important resources available online to start solving dynamic programming problems and then I will share some observations I found while solving some DP problems.

1. I started DP by understanding the basics through Algorithms by Das Gupta.It has explained DP in a very good and interactive manner and would be the best place to start.Though Algorithms by Cormen is equally good (actually better) but I find it somewhat boring and thus switched to Das Gupta.If you still have your basics loose, you can do a free course on Algorithms-part 2  by Stanford University which is available on Coursera.(It will be good to complete the whole course which is in two parts to strengthen the basics). 

2.After this you can go to GeeksforGeeks.org and visit their algorithm section.You will get lot of content on DP and that will be the best place to get a idea of scope of DP problems.

3.After this you can move to Topcoder Algorithm tutorial which is the best available tutorials online (designed by Topcoder veterans).

Here are some problems with which I have started my practice in DP.It is recommended to first try the problem yourself and then see my approach.As a beginner,it is normal if you are not able to solve first few problems.

A)See Problem

Like any other  DP question one must figure out that -

1)"how to store it"

2)"what is needed to be stored" and 

3)"how to manipulate it".

For example -

In this question, I used Hash map to store whatever i needed to store.

Now any key in our hash-map have value as a pair - counts= "MIN no. of steps to reach from current key value to input (i.e Integer K given by user) and soln="If M are min no. of steps to reach from current key to K,then how many different paths are there to reach from cur to K with exactly M steps".

Now the last step is to manipulate it -In form of recursion or iterative manner.

Observations I got from this question!!

1.Always read the question properly.Take your time.In my case I interpreted the question in wrong manner.I thought that the question has asked for total no. of possible solutions but actually it asked for no. of solutions possible corresponding to minimum no. of steps.Also it's important to not miss some small things asked in question like taking %1000000007 of your answer(no. of solutions) as asked in this problem.

2.Before coding down the problem,you should must think about your approach.In my case I used recursion technique of DP.I landed into error because I didn't even cared about input size which was 10 pow 9.It should have been obvious (had i considered this) ,that recursion technique would give a STACK  OVERFLOW ERROR.Thus It could have saved me a lot of time had I started from iterative approach in the first place.

3.There were some tricky things to catch in this problem.(Read if you have attempted the problem already.)

So the first thing to notice was that if a no. contains '0' as one of its digits then it will call

 "no. + 0" which is no. itself .Thus it will become a infinite recursion running in loops around this no.  

 Second catch to this problem was -No. of solutions corresponding to minimum steps were obtained as-

For ex- if no. is 16 then no. of solutions with no. of steps equal to min steps(let min steps to reach from 16 to 100 be M) will be as-

no. of solutions (all having steps to reach from 16 to 100 equal to M)=no. of solutions for 17(i.e no. of solutions to reach from 17 to 100 with exactly M-1 step )+ no. of solutions for 22 (i.e no. of solutions to reach from 22 to 100 with exactly M-1 step).

Now if a no. contains 2 digits with same value like 22 then it will add solution for 22+2=24 twice for each of 2's in 22.Thus it will lead to much higher answer than actual answer.

4.Even after all this I was getting 3 as no. of solutions for input 100 though answer should have been 2.I tried to figure the problem using debugger but it was a total disaster with so many recursion calls.So I used something basic to figure the problem in my answer.I inserted the print statement to print the no. of solution for every no. thus i figured out that the problem was with no. like 22 having same digits.

5.Since question demanded two things i.e. steps and solutions,I needed to return both of them.I could have done this by returning an array but it would have consumed a lot memory so I rather made a PAIR class within same java file and returned the pair.(NOTE:If u need to have 2 classes in same .java file just remove "public" from them.

6.Other noticeable thing is that its always better to use Hash map over  array in DP.Not just for DP but also whenever you need to find if no. have occurred  earlier or not (like i used for finding if no. contains duplicate digits or not).Some other observations are - initialize variable with INTEGER.MAX/MIN whenever finding max or minimum.

PROBLEM-2-SEE PROB HERE

OBSERVATIONS-

1.In this question I used Hashmap to store.Now,each hashmap entry will have key representing sum and Value of hashmap denoting no. of ways that sum can be achieved.Thus we can manipulate that -

Ways for Required sum=ways(ReqSum - arr[0]) + ways(ReqSum - arr[1]) +....ways(ReqSum - arr[n])

if arr is the list of coins available given to us

Now,answer will be very high than the actual answer.The mistake we were doing is -

Let ReqSum be 10, and array be 1,2,3,4

A1..10(-4)=10(-4)=10(-1)=10(-1)=0 ........4,4,1,1

A2..10(-1)=10(-1)=10(-4)=10(-4)=0......1,1,4,4

These two calls were counted as different ways but we can see that they are actually same combination(Just the order is different).In terms of DP, we can say that it is classical problem in which we are to choose paths which are totally different to each other (not same even when permuted) and also the paths can have repeated values as well.

Solution to this problem is that we can restrict calls such that path calls in decreasing order i.e.

 A1 will be counted while A2 won't be counted.To implement this we can take value which was considered in last call and current value that is to be taken must be smaller/equal  to that value. 

Link-https://www.hackerrank.com/challenges/stockmax

So,this problem was wrongly tagged in DP section but still i will add its solution here-

The problem can be solved by asking a question-"How is profit generated ??"..since our aim is to maximize the profit.The answer to this question is --

 For any share, you buy it and then sell it at maximum available price you can.In other words, it can be interpreted as -

If ( share price on a current day < maximum (prices of shares on subsequent days) 

/////*meaning that if you buy share on current day ,there exist some day at which you can sell this share at higher price */////

then,

buy it ///since we will be in profit 

else

////meaning that there is no greater value than today's share in coming days...which means we have to sell it in loss if we buy it...hence in this case,

sell all shares you have bought till now

(This is done because we know that  current day share value is maximum of all coming days which means that we won't get better chance to sell our shares.)

Some Observations -

1.Here I was getting answer as negative for some large sample input which was because of int overflow and thus i used long instead...But again one of the answer was coming negative....After a lot  of thinking I finally solved this problem by observing that -

money+= stockprice[n-1]*stocks;

Since money is of type long but right side will be integer (which will be overflowed before converting to long and hence negative and thus I rectified it as)-

money+=((long) stockprice[n-1])*stocks;