This will be an editorial of the FARIDA problem from SPOJ which is an basic dynamic programming problem. It is easily solved by knowing the initial states and the simple transition from previous states to the next ones.
This problem is from : http://www.spoj.com/problems/FARIDA/
Problem Statement:
Once upon time there was a cute princess called Farida living in a castle with her father, mother and uncle. On the way to the castle there lived many monsters. Each one of them had some gold coins. Although they are monsters they will not hurt. Instead they will give you the gold coins, but if and only if you didn’t take any coins from the monster directly before the current one. To marry princess Farida you have to pass all the monsters and collect as many coins as possible. Given the number of gold coins each monster has, calculate the maximum number of coins you can collect on your way to the castle.
This is the problem faced by FARIDA, a cute princess, many of you would have come across early in your adventure across dynamic programming kingdom. With an acceptance percentage of around 29%. This would be one of the easiest DP problems, but can lay the foundations to better understanding of DP states and their transition.
So, the problem basically reduces to :
Given an array, output the maximum sum of elements you can make from a subset of the array such that no two consecutive numbers from the original array are included in the subset.
Now, considering a DP[i] to be the maximum sum obtainable under such conditions till ‘i’ in the array. The DP transitions are intuitively derived as:
DP[i] = Maximum of ( DP[i – 1] ) & ( DP[i] + element ‘i’ from the array )
If we decide not to include element ‘i’ the maximum obtainable sum up to ‘i’ will be DP[i – 1]. If we decide to include DP[i] then the maximum will be DP[i – 2] + Element ‘i’, since we cant include element ‘i – 1’ in this.
So you can see how the maximum of these two values will give us the general DP recurrence. Then, the initial states easily work out to be
DP[0] = First element in array
DP[1] = Maximum of first and second elements in array.
Lastly including condition for n = 0, and n = 1, the problem is solved.
This should easily bring you an AC and 0.02 points on SPOJ as of writing the article.
The problem BadNeighbours from Top Coder is also very similar to this one.
Here is the Java code to clear things up for you:
import java.util.Scanner;
class FARIDA {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
int t = sc.nextInt();
int[] a = new int[t];
for (int j = 0; j < t; j++) {
a[j] = sc.nextInt();
}
long[] dp = new long[t];
if (t == 0) {
System.out.println("Case " + (i + 1) + ": 0");
continue;
}
if (t >= 1) {
dp[0] = a[0];
}
if (t >= 2) {
dp[1] = a[0] > a[1] ? a[0] : a[1];
}
if (t >= 3) {
for (int j = 2; j < t; j++) {
dp[j] = Math.max(dp[j - 1], dp[j - 2] + a[j]);
}
}
System.out.println("Case " + (i + 1) + ": " + dp[dp.length - 1]);
}
}
}
