编辑代码

import java.util.Arrays;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        int[][] coin1 = {
                {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> p1 = new LinkedList<String>();
        System.out.println("硬币数为：" + collect(coin1, p1));
        System.out.println("路径为:");
        printPath(p1);
        int[][] coin2 = {
                {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},
                {0,0,0,0,0,0},
        };

        LinkedList<String> p2 = new LinkedList<String>();
        System.out.println("硬币数为：" + collect(coin2, p2));
        System.out.println("路径为:");
        printPath(p2);
        int[][] coin3 = {
                {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,1}

        };

        LinkedList<String> p3 = new LinkedList<String>();
        System.out.println("硬币数为：" + collect(coin3, p3));
        System.out.println("路径为:");
        printPath(p3);
    }
    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(int i=0;i<P.size();i++)
        {
            System.out.println(P.get(i));
        }
    }
}