PolarFlea's blog

Basic DP problems
By PolarFlea, history, 5 years ago, In English

Can anyone suggest some basic DP problems (must be on Codeforces) for me to solve? I want to have a try.

  • Vote: I like it
  • -38
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think, you'd better not try according to your current rating... You'd better solve some problems using basic programming skills.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://cses.fi/problemset/list/ Dp section has some classic dp problems

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I stuck at problem Coin Combinations II and Book Shop because of TLE. I think the constrain of n upto 1e6 is the reason but i can't speed up my solution fast enough to pass all tests. Could you help me?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In coin combination my solution is O(x*n) but I implemented it bottom and bookshop is classic knapsack in O(x*n) too and you don't need to save O(x*n) state but only previous state.have you implemented your solution in top down or bottom up dp ?

      → Reply
»
5 years ago, # |
← Rev. 8   Vote: I like it +3 Vote: I do not like it

You can look this site: At Coder Dp Round:

K-tree

Cut Ribbon

I can find 2 problems for you but you can choose dp tag in codeforces and sort by difficulty level.

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

And in this link you can find many question about dp

Dp Problem Tag in a2oj

And there is a difficulty level in the near of problem.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please stop this, please.

→ Reply