Can anyone provide list of some 1d array DP problems…!!
I want as many as possible
@taran14_07
@iouzhou_101 
@ 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
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