ProblemFinding the maximum subsequence sum such that non of the elements in the sequence are adjacent to each other
One brute force approach is getting all the combinations, and excluding any combination with adjacent elements and finding the maximum from the remaining combinations. Obviously the approach is exponential. Below is the solution to solve the problem using Dynamic Programming.
In-order to solve a problem using dynamic programming there should be a solution which has optimal substructure and overlapping sub problems properties. And the current problem has optimal substructure property.
Say, f( i) is defined as maximum subsequence sum of non adjacent elements for 'i' items, then
f( i) = 0 if i = 0
Below is the algorithm for the same (note it can solved without the encapsulating data in 'record' - i just preferred it this way) - which should illustrate the above idea: