List of All 1d array DP problems..!

Can anyone provide list of some 1d array DP problems…!!

I want as many as possible

@vijju123

@sumeet_varma

@adkroxx

@usaxena95

@meooow

@ceilks

@taran14_07

@raj79

@iouzhou_101 :diamonds::diamonds:

@rachitiitr

@utkalsinha

@likecs

@ gkcs

Anyone else can also tel…!!

Its too broad of a question dear. Many dp problem needs 1-D array. Many math+combinatorics need 1-D array. 1D array is not a good criteria to differentiate problems.

1 Like

Agreed. I don’t see why you would want 1D dp problems only. A 1D problem does not mean it’s the easiest kind of dp, in case you were thinking that.

1 Like

@meooow that’s true but if you can name some 1d array dp problems because i wanted to them first :: Thank You

See this link . It has a list of many dp problems though not classified as 1d or 2d.

1 Like

Please if possible someone tell me 2-3 DP problems of 1D array

See this

1)http://www.geeksforgeeks.org/count-number-ways-jump-reach-end/

2)http://www.geeksforgeeks.org/minimum-number-of-squares-whose-sum-equals-to-given-number-n/

3)http://www.geeksforgeeks.org/longest-increasing-subsequence/

4)http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

5)http://www.geeksforgeeks.org/minimum-steps-minimize-n-per-given-condition/

This will help you I think ,thanks.

2 Likes

I know only these questions,Please if anyone else knows more 1d array problems please provide link

Why dont you use the tag feature for this? Just check for tag of “dp”. Usually it becomes obvious by constraints if 1-D dp is used or multi dimensional dp is needed.

or just check out geeksforgeeks dp section. That section is FULL of the problems you want. Most of 2D dp problems there have a 1D solution in later sections as well there. @spp___ gave you links to few problems of that section, just goto the site and check out the problems.

In the end if you are spoonfeeding yourself by avoiding the phase of deciding “This is 1-D dp with table filled like…” you will struggle in it.

Search for all problems of dp in codeforces