Arunnsit's blog

how to choose the memoization factors ?
By Arunnsit, history, 9 years ago, In English

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 . :)

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

»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

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."
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

    → Reply