编辑代码

public class MaxCoinCollection {

    public static int collectMaxCoins(int[][] coin) {
        int rows = coin.length, cols = coin[0].length;
        int[][] dp = new int[rows][cols];

        dp[0][0] = coin[0][0];
        for (int i = 1; i < rows; i++) dp[i][0] = dp[i - 1][0] + coin[i][0];
        for (int j = 1; j < cols; j++) dp[0][j] = dp[0][j - 1] + coin[0][j];

        for (int i = 1; i < rows; i++) 
            for (int j = 1; j < cols; j++) 
                dp[i][j] = coin[i][j] + Math.max(dp[i - 1][j], dp[i][j - 1]);

        printPath(dp);
        return dp[rows - 1][cols - 1];
    }

    public static void printPath(int[][] dp) {
        int i = 0, j = 0, rows = dp.length, cols = dp[0].length;
        System.out.println("收集路径：");
        while (i < rows - 1 || j < cols - 1) {
            System.out.println("(" + (i + 1) + ", " + (j + 1) + ")");
            if (i < rows - 1 && (j == cols - 1 || dp[i + 1][j] > dp[i][j + 1])) i++;
            else j++;
        }
        System.out.println("(" + rows + ", " + cols + ")");
    }

    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}};
        System.out.println("收集最大硬币数：" + collectMaxCoins(coin));
    }
}