编辑代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[][] coin1 = {
                {0,1,0,0,0,0},
                {0,1,0,1,0,0},
                {0,0,0,0,0,1},
                {0,0,1,0,0,1},
                {0,1,0,0,1,0}
        };
        LinkedList<String> p1 = new LinkedList<String>();
        System.out.println("收集硬币数：" + collect(coin1, p1));
        System.out.println("路径:");
        printPath(p1);
        
    }
    public static int collect(int[][] coin, LinkedList<String> P)
    {
        int rowcount = coin.length + 1;
        int colcount = coin[0].length + 1;
        int[][] Array = new int[rowcount][colcount];
        for (int i = 0; i < rowcount; i++) {
            Arrays.fill(Array[i], 0);
        }
        for (int i = 1; i < rowcount; i++) {
            for(int j = 1; j < colcount; j++) {
                Array[i][j] = Math.max(Array[i-1][j], Array[i][j-1]) + coin[i-1][j-1];
            }
        }
        int i = rowcount - 1;
        int j = colcount - 1;

        while(i > 0 && j > 0) {
            P.addFirst("(" + i + "," + j + ")");
            if (Array[i-1][j] > Array[i][j-1]) {
                i = i - 1;
            }
            else {
                j = j - 1;
            }
        }
        P.addFirst("(" + 1 + "," + 1 + ")");
        return Array[rowcount-1][colcount - 1];
    }
    public static void printPath(LinkedList<String> P)
    {
        for (String s : P) {
            System.out.println(s);
        }
    }
}