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…!!

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)Count number of ways to jump to reach end - GeeksforGeeks

2)Minimum number of squares whose sum equals to given number n - GeeksforGeeks

3)Longest Increasing Subsequence (LIS) - GeeksforGeeks

4)Largest Sum Contiguous Subarray (Kadane's Algorithm) - GeeksforGeeks

5)Minimum steps to minimize n as per given condition - GeeksforGeeks

This will help you I think ,thanks.

3 Likes

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.

1 Like

Search for all problems of dp in codeforces

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.

2 Likes

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

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

Counting Tower
This problem can also be solved in the 1 D approach!
Hope you understand that the DP state does not have anything related to difficulty