编辑代码

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

public class CoinCollection {

    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.println("收集到的硬币数：" + collectCoin(coin, path));
        printPath(path);
        
	}

    // 输入：硬币地图coin[][]
    //       path:收集路径
    // 输出：收集到的最大的硬币数
             
    public static int collectCoin(int coin[][], LinkedList<String> path) {
        // 1. 构建动态规划表格
        int rowCount = coin.length + 1;
        int colCount = coin[0].length + 1;
        int[][] dpArray = new int[rowCount][colCount];

        for (int i = 0; i < rowCount; ++i) {
            Arrays.fill(dpArray[i], 0);
        }
     
        //2. 填充动态规划表格
        for (int i = 1; i < rowCount; ++i) {
            for(int j = 1; j < colCount; ++j) {
                dpArray[i][j] = Math.max(dpArray[i-1][j], dpArray[i][j-1]) + coin[i-1][j-1];
            }
        }

        //3. 找到收集路径
        int i = rowCount - 1;
        int j = colCount - 1;

        while(i > 0 && j > 0) {
            path.addFirst("(" + i + "," + j + ")");
         
            if (dpArray[i-1][j] > dpArray[i][j-1]) {
                i = i - 1;
            }
            else {
                j = j - 1;
            }
        }

        path.addFirst("(" + 1 + "," + 1 + ")");


        return dpArray[rowCount-1][colCount - 1];
    }

    public static void printPath(LinkedList<String> path) {
        for (int i = 0; i < path.size(); ++i) {
             System.out.println(path.get(i));
        }
    }

}