dandf2012's blog

In DP, why state 'First i numbers' so common?
By dandf2012, history, 6 years ago, In English

In many dp, such as knapsack, there is a often a state dp[i][...] such that i is first i numbers. Why is that? Why might it be so convenient for such a state?

Tags dp
  • Vote: I like it
  • -18
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It is usually related to the way you define your dp.. But often it's easier to solve knapsack related problems using this method...

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

Or, you have solved very few problems maybe?

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

If you have some problem which

  • is easy to solve when N = 0
  • if we have answer for {X1, X2, ..., XN} then we can easily solve for {X1, X2, ..., XN, X(N+1)}

Then, to solve that problem, we first solve for N = 0, and add X1, X2, X3, and so on... This is the basic concept of DP and mathematical induction.

Of course, we don't have any reason to add it in random order, so we add from first, second, and to last.

→ Reply