What is this dP function and/or array? Is this some basic thing i haven’t studied? Any links would help. This “dP” function/array name was used by four different users in same problem (CHSIGN) in May long challenge 2018. Problem Link: https://www.codechef.com/MAY18B/problems/CHSIGN/ Answers Links: https://www.codechef.com/viewsolution/18566008 https://www.codechef.com/viewsolution/18550612 https://www.codechef.com/viewsolution/18548387 https://www.codechef.com/viewsolution/18548345 I think this would help me solve the problem too.
DP simply meant dynamic programming… It is a question of dynamic programming… Dynamic programming has many methods to solve some problems… try searching and u ll get a lot of stuff about it… here I used an algorithm for finding “maximum sum subsequence such that no two elements taken are adjacent”
This can be done in O(2^n) without using DP by bit masking (i.e checking each and every possible combination) but a very efficient way is using DP… which would be O(n)…
You can look at this link of answer of mine for soln of this problem where I explained how to solve this problem…