动态规划问题，请大家看一下

Question

两台月球矿车从A点向B点移动探测，每台矿车每次可以向右或向下移动一步，移动到的位置对应的数据为可采集的矿石数量 假设每台矿车矿石装载量无限，请求出两台矿车都到达B点后采集到的矿石数量总和最大值，并将他们经过的路径输出 动态规划问题
算法思想 代码和伪代码 复杂度（空间和时间）

Answer 1

可以当作一辆车，第一辆车先走，采集过的置为0，然后第2辆车再走。简单的动态规划问题：

class Solution{
    public static void run(int[][] arr, String name){
        List<int[]> res = new ArrayList<>();
        int row = arr.length;
        int column = arr[0].length;
        int[][] temp = new int[row][column];
        for(int i = 0;i<row; i++) {
            for (int j = 0; j < column; j++) {
                int top = i > 0 ? temp[i - 1][j] : 0;
                int left = j > 0 ? temp[i][j - 1] : 0;
                temp[i][j] = Math.max(top, left) + arr[i][j];
            }
        }
        int car = temp[row-1][column-1];
        System.out.println(name + "最大值：" + car);
        //获取car1的路径
        res.add(new int[]{row-1,column-1});
        int i = row-1,j=column-1;
        while (i >0 && j>0){
            int top =temp[i-1][j];
            int left = temp[i][j-1];
            if(top >= left){
                i--;
            }else{
                j--;
            }
            res.add(new int[]{i, j});
            arr[i][j] = 0;
        }
        while (i-- > 0){
            arr[i][0] = 0;
            res.add(new int[]{i, 0});
        }
        while (j-- > 0){
            arr[0][j] = 0;
            res.add(new int[]{0, j});
        }
        System.out.println(name + "路径：");
        for (int k = res.size()-1; k>=0;--k){
            System.out.print(Arrays.toString(res.get(k)));
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[][] a = new int[][]{{0,2,2,2,2},{0,1,0,0,2},{0,0,0,0,2},{0,0,0,0,2},{0,0,0,0,0}};
        run(a, "car1");
        run(a, "car2");
    }
}

给个采纳吧