编辑代码

   public static int collectCoin(int coin[][],LinkedList<String> path){
        // 构建动态规划表格
        int[][] dpArray = new int[coin.length][coin[0].length];
        for (int i = 0; i < coin.length; ++i) {
            Arrays.fill(dpArray[i],0);
        }
        //填充动态规划表格
        for(int i = 1; i < coin.length; ++i) {
            for(int j = 1; j < coin[i].length; ++j){
                dpArray[i][j] = Math.max(dpArray[i-1][j],dpArray[i][j-1]) + coin[i][j];
            }
        }
        int i=coin.length-1;
        int j=coin[i].length-1;
        while(i > 0 && j > 0) {
            if (coin[i][j] > 0) {
                path.addFirst("("+i+","+j+")");
            }
            if (dpArray[i-1][j] > dpArray[i][j-1]){
                i=i-1;
            }
            else {
                j= j - 1;
            }
        }
        return dpArray[coin.length-1][coin[0].length - 1];
    }
    public static void printPath(LinkedList<String> path) {
        for (int i = 0; i < path.size(); ++i) {
            System.out.println(path.get(i));
        }
    }
	public static void main(String[] args) {
        int[][] coin = {
            {0,0,0,0,1,0},
            {0,1,0,1,0,0},
            {0,0,0,1,0,1},
            {0,0,1,0,0,1},
            {1,0,0,0,1,0}
        };
        LinkedList<String> path = new LinkedList<String>();
        System.out.printIn("收集到的使币数:"+ collectCoin(coin,path));
        printPath(path);
	}