题目

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

一、暴力递归

递归含义: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);
    }

二、动态规划

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

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

在dp中:

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

递归:

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

在dp中

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

总代码

    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];
    }