amsen's blog

How to become strong in DP
By amsen, history, 9 years ago, In English

How to become strong and expert in DP ?

can any body tell me some problems and some links to read ?

thanks all!

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

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

DP for Dynapic Programming?

→ Reply
»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I suggest to you reading this article with practicing examples mentioned in it.

https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I'd suggest you reading Nicolaus Wirt — "Algorithms and Data Structures". Chapter "Dynamic Programming"

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

Practice makes perfect.

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

The core of DP is to turn the problem into a formula, to generate an new algorithm. It is likely that 100 DP problems have 101 formulas(by my friend). So actually, the only way to improve DP skill is to practice more and AC different kind of DP.

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

    could you please say me some problems in any online judges?

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

      (⊙ˍ⊙)I'm a Chinese ACMer, I mainly solve some problems on Chinese OJ. You can find many DP problems through the tag in 'Problem Set' on CF. I learn my DP skill on this page problem ID 1003(largest sub-string) 1081(largest sub-rectangle) 1159(longest common sub-sequence) 1025(longest increasing sub-sequence) 2602 1059(two package problem) is some primary problem. If you are satisfied with the problem, you may solve other problem on the list, just skip ones with Chinese description. It may be hard for you to find the solution as you can't read others' solution on HduOJ. HUST is another big OJ in China, you may register an account and search the solution in 'STATUS' (OJ 'HDU' 'Accepted'), you can see the code of solution by clicking green ones below language.

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

      Any tips to improve everything including dp?.. except practice what else??

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

        except practice what else??

        Get a brain transplant (if that is even possible). That's pretty much all you need. My condolences that God didn't give you a brain that is as good as those of red coders. Lmao.

        On a more serious note, please get a life. Not everyone is suited for CP.

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

Just with one thing. "Practice"

There are lots of problem about DP on codeforces , LightOJ or other websites.

You can start with easiest one. Then you will see you are improving day by day.

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

solve the problems in these answers on Quora

when you are thinking about the solution try to solve it with recursion and memorization,don't submit the recursion/memorization solution,after your solution is right you can easily convert it to DP.

Don't forget to practice a lot ,because better results needs hard working :)

I'm telling you to do this because this is the strategy to start DP(because DP is an optimization for recursion),sorry for my bad English.

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

    Is there any resource how to convert memoization to DP?

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

      Just think about what dp results you need to construct some larger dp result. In recursion, you would say something like:

      dp(k)= dp(k-1) + dp(k-2)

      If you think about program flow, once the function dp hits its base cases, then it starts returning answers to increasingly larger problems. So you know later indices depend only on earlier ones, so you iterate from earliest to latest indices in your recursion.

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Try reading this...

      Read some solutions in recursion and DP (the solution is for the same problem) and you'll understand... It may be hard in the beginning...,but don't stop practicing :)

      sorry for my bad English

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

Now you are master can u tell how u did it??

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

Here some questions. My teacher gave them to me. And I be better at Dp.

Number of ways

Daemon and wifi

given length and sum of digits

quasi binary

Boredom

ultra-fast mathematician

soldier and number game

Flowers

Password

Caesar's Legions

Barcode

Mr. Kitayuta, the Treasure Hunter

Pashmak and Graph

Red-Green Towers

Little Pony and Harmony Chest

Hope you enjoy :))

→ Reply
»
3 years ago, # |
  Vote: I like it -79 Vote: I do not like it

I can teach you lessons on dp. But it will cost 100$ per lesson. Believe me you'll be the best in dp.You maybe will beat tourist after my lessons.

→ Reply
»
3 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Since necroposting this became the new thing, i just want to point out how cool it is to see people blogs of people asking relatively simple stuff that became orange/red a couple of years later

→ Reply