Блог пользователя PolarFlea

Basic DP problems
Автор PolarFlea, история, 5 лет назад, По-английски

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

  • Проголосовать: нравится
  • -38
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 ?

      → Ответить
»
5 лет назад, # |
← Rev. 8   Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить
»
5 лет назад, # |
← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please stop this, please.

→ Ответить