hippie's blog

Conceptual Doubt regarding "state" in Dynamic Programming
By hippie, 10 years ago, In English

Should a state in DP be viewed as

1) a description of current scenario (e.g. in knapsack problem -->I am on item 'i' with having filled the bag with 'j' units) 

OR as

2) a separate sub-problem (e.g. in knapsack problem -->maximum value that can be attained with weight less than or equal to 'j' using items upto 'i' (first 'i' items) )

I have seen both the interpretations used many times and I would welcome some opinions regarding the same.

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

Comments Comments (1)
| Write comment?
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

When I'm solving a problem I have both in mind. On different problems I find different ways to be more intuitive, so they're surely both correct and purely in my opinion it's not good to stick strictly to only one of them, as it may sometimes turn out to be confusing.

→ Reply