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

how to choose the memoization factors ?
Автор Arunnsit, история, 9 лет назад, По-английски

hello everyone! i am a newbie and trying to learn dynamic programming , i find it easy to write a recursive solution but it i find it difficult to memoize it. or you can say , that i am unable to judge on what factors dp state depends . any help would be appreciated . :)

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

»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

If you are confused with choosing such "factors", then you didn't fully understood dynamic programming since you are simply writing brute force search.

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

I recommend you to read the response of Mimino in Quora here.

In special this part:

"Here are some restrictions I put on a backtrack solution:

  • it should be a function, calculating the answer using recursion
  • it should return the answer with return statement, i.e. not store it somewhere
  • all the non-local variables that the function uses should be used as read-only, i.e. the function can modify only local variables and its arguments."
→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    I don't see how DP/memoisation relates to backtracking. They're two different techniques. Why did you highlight that?

    → Ответить