lichen782
BAN USERLet dp[i][j] be the max value from ith and jth bomb on the circle, forcing i no greater than j.
Actually by denoting any kth (i <= k and k <= j) bomb, we got a precisely sub problem with smaller size, such that:
dp[i][j] = Max{ dp[i][bkd] + v[i] + dp[fwd][j] } , where bkd and fwd is by denoting kth bomb, the backward and foward range that not get effected.
Note this is a circle, sequence does matter, so dp[i][j] assumes from i to j, there are bombs, but from j to i, no bombs.
public class BombGame {
/**
* @param args
*/
public static void main(String[] args) {
BombGame bg = new BombGame();
System.out.println(bg.maxValue(new int[] {1, 3, 2}, new int[] {1, 1, 0}));
}
private int[] v;
private int[] r;
private int length;
private int[][] dp;
public int maxValue(int[] v, int[] r) {
this.v = v;
this.r = r;
this.length = v.length;
this.dp = new int[length][length];
for(int i = 0; i < length; i++) {
dp[i][i] = v[i];
}
return maxValueInternal(0, length - 1);
}
private int maxValueInternal(int start, int end) {
if(start > end) return 0;
if (start == end || dp[start][end] != 0)
return dp[start][end];
for (int i = start; i <= end; i++) {
// denote i
int fwd = i + r[i] + 1;
int bkd = i - r[i] - 1;
//this is a little tricky, as we have to consider
//when the range is very big, it destroy the end
//bomb, thus changing the end range
int end_ = (bkd + length) % length;
end_ = end_ < end ? end_ : end;
dp[start][end] = Math.max(dp[start][end],
maxValueInternal(start, bkd) + v[i] + maxValueInternal(fwd, end_));
}
return dp[start][end];
}
}
Repnoradweisser, Backend Developer at ASU
I am Nora, I am a writer, I write many types blogs and articles. I collected many types and astrology ...
RepTristaRJohn, Reverse Engineering and System Developer at BT
I am an Ophthalmic medical assistant in bluefield USA, I assist in retinal exams and procedures. Referred patients to outside ...
Repraginieharris, IIT Exam at Altera
I am Ragini, and I have lived in Washington for 2 years. My current job is Web Designer in Corinthian ...
Repcarmenrhargis, Associate at Achieve Internet
Hi, I am Gladys, I live in Florida, USA, I am working as a project manager in a Life’s ...
RepEvieBBlack, AT&T Customer service email at ASAPInfosystemsPvtLtd
I am Evie from Santa Fe Springs USA, I am working as a manager in a worldwide company. I also ...
Repaaronmdunlap6, Area Sales Manager at Achieve Internet
Hi, I am an HR Analyst with extensive experience delivering innovative solutions at the corporate level. Expertise in employee relations ...
Rephollymclark8, Apple Phone Number available 24/7 for our Customers at Accenture
I am clinical laboratory technologist in Stratapro company. I have Excellent clinical laboratory skills, with commended performance conducting/analyzing laboratory ...
Repjoycepwise, Blockchain Developer at Accenture
Hello, I’m Joyce. I’m a business developer living in Tampa, FL. I am a fan of music, travel ...
@Miguel, you are right. As sequence matters, we can't simply split this circle in 2 parts and calculate them serperately. Maybe we have to use some sort of brute force.
- lichen782 September 22, 2013