Dynamic Programming : SPOJ EDIST

Here are two of my solutions to the EDIST problem on SPOJ.

  1. Fist one is Recursion with Memoisation. Find here
  2. Second one is same as first but implemented through an iterative approach. Find here

Both Solutions being almost same, why does the first one give TLE?

PS : I am a newbie to Dynamic Programming. Some good simple questions of DP will be helpful. Don’t mention any tutorials please (just questions).

Thanks in Advance.

The first one recursion with memoisation uses more memory, since during each recursion a separate memory is required for every variable.

Although both solutions look perfectly fine.

Try this link for more info on DP

Your recursive solution needs minimisation. Here

  1. Firslty, You must use array[] instead of
    map<> because access time of array
    is more faster than map<> or even
  2. Secondly there is no need of extra array op[] that you have been used here.
  3. Thirdly there is no need to pass string a, string b in function as it unnecessary takes too much time for initialising and assigning the values again and again.

See my accepted code. I just modify your code little bit.


Thank You @bansal1232

Off topic but why would someone post this and delete it within minutes?
I am talking about @cosmosh answer

@cosmosh I am interested.

alt text

@shraeyas why do you use map? What added advantage do you get other than TLE? Just curious!

1 Like

Either an admin was on, who saw and deleted it, or perhaps that poor guy was trying to answer with code or something but some error occurred.

Someways it used to seem easy because the default value is set to zero and also does not give segmentarion fault, but now I guess there are disadvantages too. Will stop using that and try to stick to arrays.




or maybe trying to inject a script, which did not work :stuck_out_tongue:

i checked his profile and one of his previous answers also seem like some ‘koi mil gya’ codewords. :stuck_out_tongue:

BTW, you said that you want questions. So What type of questions have you already practiced?

The typical easy dp problems involve-

  • Finding Length of Longest Increasing Sub-sequence

  • Finding Maximum sum of contiguous sub-array in an array of positive and negative integers.

  • Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).


Hackerearth also has a good section of dp problems, with labelling as “easy” etc. Though I will say that practice some standard algorithms first before attempting them.

The way I found best for dp was that first get the concept of 3-5 algo, like LIS, LCS &etc. and then try to apply them in a practice problem. You will soon find yourself thinking and applying dp solutions naturally. Its just a matter of practice and getting used to it.

1 Like

Lol XD. He is a spammer anyways. He will get banned soon.

I have done simple questions on spoj like COINS and FARIDA.

Just wanted to have more grasp on how to determine whether a question requires DP Approach or not.

Thanks for your resources. :slight_smile:

Which type of algos have to seen? Like LIS, LCS, Cutting a rod etc.

That will help me in sorting the Q which I can give to you. :slight_smile:

just take me as a beginner.

Assume that I haven’t seen any XD

Then I suggest you to look them here - http://www.geeksforgeeks.org/fundamentals-of-algorithms/#DynamicProgramming

It consists of “standard DP problems” and their algorithm/solutions. It is advised to try the Q first, and then look at how they solved it. Since the detailed answers are provided, I feel this should help you. :slight_smile:

1 Like

Saw another of @cosmosh post on a different question where he posted the link to edit that comment which he made here.

I guess he was thinking this would execute that script :expressionless:

Dont know much about this stuff, bear with me.

1 Like

Thanks @vijju123

1 Like

Eve I don’t know much about it. Its better to report it to @admin and leave it to them. :slight_smile:

1 Like

There is no way to get your hand in DP. The only you can do is to practice. If you think you can get perfection in DP by applying some problems in DP then you are wrong. DP problems needs practice and most important is imagination and nothing else. So whenever you got such DP problems then try to make recursive optimal substructure and then relate it with real situation.

1 Like