questions to solve for learning dynamic programming basics

Can someone suggest me the series of questions to solve in sequential order to learn dp from basic to advance?

How much are you into dp? Some of the standard Q are-

  • Longest increasing sequence - LIS

  • Maximum sum contiguous sub-array (Contiguous Sub-array with maximum sum). Given an array, print the find the maximum sum a contiguous sub-array in it can have. Eg- if A= {1,2,3,4,5} , the sum is 1+2+3+4+5=15. If A={1,2,-9,4,5}, then the sum is 4+5=9. If a={-1,-9,-3,-4,-5}, then max sum is -1. (considering only {-1} in sub-array, i.e. length of sub-array can be 1)

Then we have this one-

  1. 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).

Then SPOJ’s ALTSEQ question is also nice for beginners.

Once you do this, you will find your thought process getting used to dp.

Hint to approach them-

Ask yourself 2 important question-

  • What things/calculations are getting
    repeated when I solve the problem?
  • How can I use the previously computed
    sub problems to find the next sub
    problem?

Its useful if you solve LIS first. Its ok if you look at its algo after repeated failed attempts. Make sure you understand it thoroughly, because the same concept would be tested by other problems!

As @vijju123 wrote, Longest increasing sequence - LIS and Kadane’s algorithm (Maximum sum contiguous sub-array) are some basic algorithms in dynamic programming.

If you wanna go further Mo’s algorithm and Dijkstra’s algorithm are also very important in competitive programming, they are basically graph searching algorithm.

Problems:

  1. Tourists in Mancunia (Graph theory)
  2. Primitive Queries (Mo’s Algorithm)
  3. Interval Game (Dynamic Programming)
3 Likes

Yes, you are right. These are also important!

1 Like

@hars123
Learning dp can be more easy by going through video tutorials of basic and standard problems…
Apart from problems told by @vijju123 and @only4, subset sum problem, knapsack problem, edit distance etc. are some basic problems.
First try your hand on them and then u can go to advanced questions :slight_smile:

1 Like