This question is already asked:
https://stackoverflow.com/questions/29249104/maximum-sum-in-ipl-matches
Problem Statement: https://www.codechef.com/ZCOPRAC/problems/ZCO14004/
Bonus/Similar link: https://discuss.codechef.com/questions/55874/iplzco-2014
Prerequisite: I am beginner in dynamic programming and algorithm.
As I understand till now solving a problem via dynamic programming require breaking into sub-problems and reusing the result of the problem solved.
The problem is solved via DP based on the comment and answers on various links related to the same context.
There is a complete & working solution for the problem :
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[] = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
int sum = 0;
for (int i = 0; i < n; i++)
sum = sum + arr[i];
int min[] = new int[n];
min[0] = arr[0];
min[1] = arr[1];
min[2] = arr[2];
for (int i = 3; i < n; i++)
min[i] = arr[i] + minimum(min[i - 1], min[i - 2], min[i - 3]);
int val = sum - minimum(min[n - 1], min[n - 2], min[n - 3]);
System.out.println(val);
Note: function minimum(a, b, c) returns minimal number of parameters passed.
I don't understand how this solution works (Proof of solution). How does it break into subproblems and compute result (if it is DP)?
How should we propose the solution of the problem via DP (if possible)?
Let $X_k$ be the largest sum up to the k-th element that follows the rules and doesn't include the k-th element itself. Let $Y_k$ be the largest sum up to the k-th element that follows the rules and includes the k-th element itself, but not the one before. Let $Z_k$ be the largest sum up to the k-th element that follows the rules and includes the k-th element itself, and the one before as well. Let $a_k$ be the array elements. Then $X_{k+1} = max (X_k, Y_k, Z_k)$, $Y_{k+1} = X_k + a_{k+1}$, and $Z_{k+1} = Y_k + a_{k+1}$. Start with $X_0 = Y_0 = Z_0 = 0$, calculate $X_n, Y_n, Z_n$ and the solution is $max (X_n, Y_n, Z_n)$.
How this solves the problem/works/breakdowns-into-subproblem?
