图解

代码实现

package com.kuang.study.lanqiao;


public class Main {
    public static void main(String[] args) {
        int n=8;//机器人个数
        int[] pre={0,0,0,0,1,0,2,3,5};//选择这个工作后的其那句最近工作下标
        int[] profit = {5,1,8,4,6,3,2,4};	//工作收益
        int opt[]=new int[n+1];

        opt[0]=0;

        for (int i = 1; i < opt.length; i++) {
            opt[i]=Math.max(opt[i-1],opt[pre[i]]+profit[i-1]);//比较2种方案，选择和不选择，取收益最大的方案
        }

        for(int i=1;i<n+1;i++){
            System.out.println(opt[i]);
        }

    }
}