出处 https://www.bilibili.com/video/BV18x411V7fm
题解 https://www.cnblogs.com/AzrDream/p/12264719.html
个人代码:
/**
* @author Zhai
* 2020/8/15 15:49
*/
public class Test {
public static void main(String[] args) {
int[][] input = new int[8][3];
input[0] = new int[]{1, 4, 5};
input[1] = new int[]{3, 5, 1};
input[2] = new int[]{0, 6, 8};
input[3] = new int[]{4, 7, 4};
input[4] = new int[]{3, 8, 6};
input[5] = new int[]{5, 9, 3};
input[6] = new int[]{6, 10, 2};
input[7] = new int[]{8, 11, 4};
System.out.println(dynamic(input));
}
public static int dynamic(int[][] input) {
// 优化
if (input.length == 0) {
return 0;
}
if (input.length == 1) {
return input[0][2];
}
// 每个任务如果做之后, 那么前一个可做的任务
int[] pre = new int[input.length];
for (int z = input.length - 1;z >= 0;z--) {
if (z == 0) {
pre[z] = -1;
}
// b为前一个可做任务的index
for (int b = z - 1;b >= 0;b--) {
if (input[b][1] <= input[z][0]) {
pre[z] = b;
break;
} else if (b == 0) {
// 如果b为0,且不满足上面判断条件,则前面没有任务
pre[z] = -1;
}
}
}
int[] dp = new int[input.length];
// 初始化边界
dp[0] = input[0][2];
for (int i = 1;i < input.length; i++) {
if (pre[i] == -1) {
dp[i] = Math.max(input[i][2], dp[i - 1]);
} else {
dp[i] = Math.max(dp[pre[i]] + input[i][2], dp[i - 1]);
}
}
return dp[input.length - 1];
}
}