-
Notifications
You must be signed in to change notification settings - Fork 0
/
NinjasTraining.java
68 lines (56 loc) · 2.08 KB
/
NinjasTraining.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
package Dynamic_Programming;
import java.util.Arrays;
public class NinjasTraining {
public static int ninjaMemo(int[][] arr, int day, int last, int[][] dp){
if (day == 0){
int max = 0;
for (int task=0; task<3; task++){
if (task != last) max = Math.max(max, arr[0][task]);
}
return dp[day][last] = max;
}
if (dp[day][last] != -1) return dp[day][last];
int max = 0;
for (int task=0; task<3; task++){
if (task != last){
int points = arr[day][task] + ninjaMemo(arr, day-1, task, dp);
max = Math.max(max, points);
}
}
return dp[day][last] = max;
}
public static int ninjaTab(int[][] arr){
int n = arr.length;
int lasts = arr[0].length+1;
int[][] dp = new int[n][lasts];
for (int i=0; i<n; i++){
Arrays.fill(dp[0], -1);
}
// base cases
dp[0][0] = Math.max(arr[0][1], arr[0][2]);
dp[0][1] = Math.max(arr[0][0], arr[0][2]);
dp[0][2] = Math.max(arr[0][0], arr[0][1]);
dp[0][3] = Math.max(arr[0][0], Math.max(arr[0][1], arr[0][2]));
for (int days = 1; days < dp.length; days++){
for (int last = 0; last < 4; last++){
dp[days][last] = 0;
for (int task = 0; task < 3; task++){
if (task != last) {
int point = arr[days][task] + dp[days - 1][task];
dp[days][last] = Math.max(point, dp[days][last]);
}
}
}
}
return dp[n-1][lasts-1];
}
public static void main(String[] args) {
int[][] arr = { {10, 40, 70}, {20, 50, 80}, {30, 60, 90} };
int[][] dp = new int[arr.length][4];
for (int i=0; i<arr.length; i++){
Arrays.fill(dp[i], -1);
}
System.out.println(ninjaMemo(arr, arr.length-1, 3, dp));
System.out.println(ninjaTab(arr));
}
}