### nrg_aceu's blog

By nrg_aceu, history, 6 weeks ago,

I've practiced for dp and i have found my weakness.its the dp state.somehow i never guessed it correctly.the states that i made was never relevant to the actual answer.its totally wrong.i have no clue whenever i try to make some dp states and just see if somethings correct.idk how poeple just solve dp like its 1+1.i do not know what do memoize.can someone help me?

• -33

 » 6 weeks ago, # |   -6 pls help
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 The more you practice the more intuitive it becomes, most of the time the dimensions depend on the parameter in your recursive approach.
•  » » » 6 weeks ago, # ^ |   -10 oh wow practice! why i didnt think of that -_-
•  » » » » 6 weeks ago, # ^ |   +1 Is there any other secret I am unaware of?
•  » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 then why not try it? This helped me a lot.
•  » » » » » 6 weeks ago, # ^ |   0 nope,already tried
 » 6 weeks ago, # |   -9 Welp,guess nobody is helpful
 » 6 weeks ago, # | ← Rev. 2 →   +3 "the states that i made was never relevant to the actual answer" its because one should not guess dp states, instead one should derive it using recurrence relation.
•  » » 6 weeks ago, # ^ |   0 How? or perhaps my elaboration is not that clear.lemme make an example.take a classical LCSwe have 2 strings.with those strings we need to check the lcs.ofc bruteforce will come to mind first but it requires tons of loops and other things.WIth dp,we need to observe.but whenever i observe,its wrong.like for example,what do we need? the position of a specific characters? the number of occurence of a letter? the length? well idk unless soomeone tell me what matters.i would always guess.lcs might be a bit obvious but think about more advance
•  » » » 6 weeks ago, # ^ |   +3 You need "prefix of the array / string" as a state in $90\%$ of problems.
•  » » » » 6 weeks ago, # ^ |   0 what about other types
 » 6 weeks ago, # |   0 Think like this — Let currently you are at index i so what are the necessary information you should know from previous values to calculate the answer of current i, those informations will be your state of dp. You can always optimise your states from here.