This will most likely be my last blog about dp since i have given up on cp communities.noone is helping me nor even caring to me.whenever i ask someone they think im just trolling when im being dead serious.
dynamic programming,what is it? dynamic programming is the technique of optimization.instead of bruteforcing,we can just do dp.which is convenient.there are 2 ways.recursion with memoization and filling arrays(basically all memoization).
sounds simple right? lets move on to the example.there are alot of classical dp problems like 0-1 knapsack,prefix sum,catalan numbers and so on.it might be hard if u do them for the first time.but as time goes on,it will become easier.
now to the real deal.how to do it in contest when its not classical problems.like modified knapsack wheremaybe 1 item cannot be taken twice or maybe every i-th taking process some value will cut down into n/2 because of some reason and many more.now you are solving a brand new problems.can you? this is equivalent of making a brand new algorithm,but in this case its just modifying but still it requires thinking and impossible to do within contest time.
most tutorials will say identify,think about states and youre done.yea thats it.thats basically what dp is about.but about getting the exact states that the problem wants? im not so sure if everyone can do that unless by doing similar problems(not classical but the exact same type of problem that is given to you).
what ur going to do in this situation? ask? if you have someone that u can rely on then good,it would be easy.but what if someone just trolls you everytime and ignore you because they are better than you and not worht of their time? do u think this is just beyond rude?.u will just fall into the pit of desperation and cant do anything since you cant adapt and noone is guiding.u will just become a cheater if u are really desperate to have better(i think most cheater are in this case,correct me if im wrong).but for someone that doesnt want to cheat and improve purely? how? like a clueless baby that try to stay alive without a parent,u will eventually fail.trust me,u will.u will just make a blog on how to improve and people will say u suck,not worth of cp and probably tell you just quit cp ur not smart enough.
the point of making this blog is just to remind people that sometimes,learning an algorithm is not worth your time.its just really abstract that people just make random proof for the sake of editorial content.
perhaps someone can convince me that dp is not that hard? but i think at this stage noone will ever change my mindset.
goodbye
