Given a 2D array with size N, I want to maximize array[0][k1] + array[k1 + 1][k2] + array[k2 + 1][k3] + ... + array[kx + 1][N - 1] for a given x. All k values are strictly increasing.
With small values of x (x = 2, 3, 4), a dynamic programming solution appears feasible.
However, the bound is 1 <= x, N <= 100, so I am not sure how to attempt this.
Assuming that we are at a particular state (ki, xi) with ki is the current k index, x is the last k in order to give the answer for the problem, we need to try to find the maximum value we can create from this state.
We make one observation that the problem can be divided into subproblem (ki, xi). As for each (ki, xi) state, the result is independent of previous state, we can have our formula:
For ki == x, answer = 0
Otherwise, (ki, xi) = array[xi][z] + max(ki + 1, z) with z > xi
Here is a simple pseudocode
int[][]dp;
boolean[][]check;
boolean maxAmount(int k, int x){
if(k == X){
return true;
}
if this state is visited {
return check[k][x];
}
boolean result = false;
for(int i = x + 1; i < n; i++){
if(maxAmount(k + 1, i)){
result = true;
dp[k][x] = max(dp[k][x], array[x][i] + dp[k + 1][i]);
}
}
return check[k][x] = result;
}
Note: For the special case when we cannot find enough k, you need to handle it depending on the requirement, but it should be trivial.
(ki, xi, yi) is independent of previous state, thus we can use it as our dp statex k, it depends on your specific problem.
x, and what is the size of the inner N arrays?a[0][k1] + a[1][N-1]xis inkxmeans number ofk? Can you describe more about yourdpapproach? I think using thedp[x][n][n]should work? O(n^4) with n = 100 is not bad.