KMP

Good Example to remember

pattern: ABCDABD

target: ABCDAB ABCDABD

ABCDABD

ABCDABD

next table:

ABCDABD for D you have 2 since the string your are looking for is

ABCDAB ABCCAB doesn’t make 3

How to build next:

1. first two place is special, then left move by 1 then keep search

2. keep searching until equal

Then with the next array how to match

Both two string pointer should be valid, finally the target string should be iter throughed totally

BackPack

  1. basic backpack question, use reachable method to solve it


    pay attention to the derive operation, even some new added number has no help, the place can still be true because of the derive operation

  2. backpack with value, same solution


    also should pay attention to the derive relationship among them

  3. Minimum Adjustment Cost

    1. Firstly, we can use recursion to solve it

      cannot use the simple cache, since the parameter not only has included current index, but also some precondition
      Even though lots of continue to jump through, but still lots of repeating computation

    2. Secondly, the dp just layout all the memory footprint using lowerbound, and upperbound

    3. Finally the space complexity can still be reduced