its been a while since i have written a blog, i am going to try to be consistent this time even though i have my end sems coming up, i know this is trashy idea but ima do it either way.
i was siting in cozy lab and two nigs pulled up beside me and opened up their rotten lunchbox and took whoping 30 mins to finish that abomination of a lunchbox. like damn bro go eat in an empty classroom, why you gotta eat in a lab where ppl work and on top of that beside me.
I am going to start my journey of icpc seriously this time, you all know how i slacked after my june-july arc but aint gona happen this time, you will see my every progress. i have also noticed i am been gulping fast/junk food alot every single week, its kind of bingeeating ima stop that.
now lets talk about my studies im currently doing 0/1 knapsack. its already known concept. but lets see if theres anything else i can extract from this. four ways to do this:
1. Recursion.
2.memoisation(top down dp).
3.tabulation method(bottom up dp)
4.space optimised dp
recursion step is easy, summary: either you select the weight or not. as simple as that and after every recursion call finishes you simply calculate the max of notpicked weight and pickedweight. aka going through all possible combinations and storing their value. time complexity: 2^n.
alright i completed the memoisation and tabulation part after both of these space optimised dp becomes self obvious.
difference between tabulation method and space optimised dp is ALOT. its like an ant infront of an elephant, the tabulation method is like a 2d array where you store all the values of the dp and space optimised dp is like a 1d array where you store only the last row of the dp.
knapsack has many types like mixed ,complete and multiple. you can give it a read from this article its great, also refer this for code reference and approach
although so far in cp no need to go that deep for knapsack, i will go deep in this topic after practical exams are over rn am covering as much as i can for both practicals and cp alike.
theres also this topic "matrix multiplication" which is also an application of dp, its overall boring stuff i will have to search for its questions somewhere. aight see ya!!! .
follow my everyday blogs, youre going to witness my life ramming and unfolding infront of your eyes!!
© 2026 My Simple Blog