Please help! Frequently coming doubt to my mind in one famous DP(Knapsack) problem ??
Difference between en1 and en2, changed 31 character(s)
Hello, It can seem strange to ask this question to some of you but I am actually not getting convinced or not something very obvious is not enough intuitive to me. So below is the problem : ↵

The question: Why in knapsack we always chose prefix instead of something like range (l,j). Before you get angry please read my full question. ↵

Like how we are so sure that in taking the prefix of the items we are going to consider all the cases possible that are also lying same if we consider range of the items. ↵

[
YouAtcodetext to link here...ample problem](https://atcoder.jp/contests/abc282/editorial/5419)↵
 ↵
Like in this problem we have to count the different pairs of permutations whose similarity is equal to K .↵

In the editorial,
 **DP is defined by considering the prefix instead of something like range (I,J)**. And this is not intuitive to me ?↵

So in a way the question can be rephrased as **How we have to decide in DP when to take prefix and when to take range of the array**  with the **thought in mind that no cases are left out as in case of the above problem example I have given??**↵

If any one can reply it will be of great help to me as this part is not very intuitive/convincing to me.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English helloworld1102 2023-10-14 22:31:59 11 Tiny change: 'bvious is not enough intuitive' -> 'bvious is intuitive'
en2 English helloworld1102 2023-10-14 22:30:48 31
en1 English helloworld1102 2023-10-14 22:29:51 1283 Initial revision (published)