Cheap_try's blog

Need Help
By Cheap_try, history, 16 months ago, In English

Can you please give me a list of some simple 1-D dynamic programming problems which you did or practiced when you start learning dynamic programming.

thank you in advanced.

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/gym/103149/problem/A

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Starting problems of cses DP Section, Atcoder DP first few and random DP tagged codeforces problem (may or may not be very educational), here is one. You can find some gym contest made by errichto or other coders too on codeforces. You can find one of them in this blog.

Also a suggestion, it would be better to understand why you need 2D or more dimension "dp array" in first place. You will build intuition as you practice but having less DP states doesn't make a problem any easier.

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

  1. Atcoder Educational DP Contest

  2. Codeforces Gym Problemset

  3. Marathon DP vjudge

→ Reply
»
16 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

usaco guide

Here are the best resources to learn anything

You can find a DP in the gold Section

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

You can try (some problems require something like dp[n][2] or dp[n][4])

https://codeforces.net/contest/180/problem/C https://codeforces.net/contest/234/problem/C https://codeforces.net/contest/1420/problem/C1 https://codeforces.net/contest/1526/problem/C1 https://codeforces.net/contest/166/problem/E https://codeforces.net/contest/545/problem/C https://codeforces.net/contest/1272/problem/D https://codeforces.net/contest/1061/problem/C

Or just dp-tagged problems with difficulty from 1200 to 1500

→ Reply