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

Автор hippie, 9 лет назад, По-английски

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.

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

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

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.