array/function name: dp. What is this? Problem: CHSIGN

array
function

#1

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.


#2

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…


#3

hi can you help me in finding the list of element that produce max sum in “maximum sum of non-contiguous elements in array”