编辑代码

package homework;
import java.util.Arrays;
import java.util.LinkedList;

public class CoinCollection {
    // 输入：硬币地图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));
        }
    }

    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);
    }
}