---

题目

现有司机N*2人，调度中心会将所有司机平分给A、B两个区域
第 i 个司机去A可得收入为income[i][0]，
第 i 个司机去B可得收入为income[i][1]，
返回所有调度方案中能使所有司机总收入最高的方案，是多少钱

一、暴力递归

递归含义:index可以去A区或者B区,A区还剩rest个名额
递归basie key:
1)没有司机可以选,返回0,
2)A区名额已满,司机只能去B区
3)B区名额已满,司机只能去A去

	public static int maxMoney(int[][] income) {
		if (income == null || income.length < 2 || (income.length & 1) != 0) {
			return 0;
		}
		int N = income.length; // 司机数量一定是偶数，所以才能平分，A N /2 B N/2
		int M = N >> 1; // M = N / 2 要去A区域的人
		return process(income, 0, M);
	}

	// index.....所有的司机，往A和B区域分配！
	// A区域还有rest个名额!
	// 返回把index...司机，分配完，并且最终A和B区域同样多的情况下，index...这些司机，整体收入最大是多少！
	public static int process(int[][] income, int index, int rest) {
		if (index == income.length) {
			return 0;
		}
		// B区满了
		if (income.length - index == rest) {
			return income[index][0] + process(income, index + 1, rest - 1);
		}
		//A区满了
		if (rest == 0) {
			return income[index][1] + process(income, index + 1, rest);
		}
		// 当前司机，可以去A，或者去B
		int p1 = income[index][0] + process(income, index + 1, rest - 1);
		int p2 = income[index][1] + process(income, index + 1, rest);
		return Math.max(p1, p2);
	}
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

二、动态规划

dp[i][j]含义:有i个司机,A区还有j个名额,最大收入是多少
根据递归Basie Key:
递归

	if (income.length - index == rest) {
		return income[index][0] + process(income, index + 1, rest - 1);
	}
1
2
3

在dp中:

	if (N - i == j) {
		dp[i][j] = income[i][0] + dp[i + 1][j - 1];
	}
1
2
3

递归:

	if (rest == 0) {
		return income[index][1] + process(income, index + 1, rest);
	}
1
2
3

在dp中

	if (j == 0) {
		dp[i][j] = income[i][1] + dp[i + 1][j];
	}
1
2
3

总代码

	public static int maxMoney2(int[][] income) {
		int N = income.length;
		int M = N >> 1;
		int[][] dp = new int[N + 1][M + 1];
		for (int i = N - 1; i >= 0; i--) {
			for (int j = 0; j <= M; j++) {
				if (N - i == j) {
					dp[i][j] = income[i][0] + dp[i + 1][j - 1];
				} else if (j == 0) {
					dp[i][j] = income[i][1] + dp[i + 1][j];
				} else {
					int p1 = income[i][0] + dp[i + 1][j - 1];
					int p2 = income[i][1] + dp[i + 1][j];
					dp[i][j] = Math.max(p1, p2);
				}
			}
		}
		return dp[0][M];
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19