如何实现Java中类似Python的数组合并，完成零钱兑换DP代码迁移

首先替换存储硬币组合的结构：Java原生数组长度不可变，无法直接拼接元素，我们使用可变的List<Integer>存储单个金额对应的硬币组合，外层用List<List<Integer>>存储所有金额的组合结果，完全对齐Python的列表操作逻辑。

核心代码行对应实现 #

你需要迁移的Python代码：

coins_results[i] = coins_results[i-coin] + [coin]

对应的Java实现逻辑：

// 先复制i-coin金额对应的硬币组合
coinsResults.set(i, new ArrayList<>(coinsResults.get(i - coin)));
// 再追加当前硬币到组合末尾
coinsResults.get(i).add(coin);

完整Java实现代码 #

import java.util.ArrayList;
import java.util.List;

public class CoinChange {
    public static List<Integer> change(int[] coins, int amount) {
        // 存储每个金额对应的最少硬币数量，初始值设为不可能的最大值amount+1
        int[] result = new int[amount + 1];
        for (int i = 1; i <= amount; i++) {
            result[i] = amount + 1;
        }
        result[0] = 0;

        // 存储每个金额对应的硬币组合，初始每个位置都为空列表
        List<List<Integer>> coinsResults = new ArrayList<>();
        for (int i = 0; i <= amount; i++) {
            coinsResults.add(new ArrayList<>());
        }

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i >= coin && result[i - coin] + 1 < result[i]) {
                    result[i] = result[i - coin] + 1;
                    // 对应Python的列表拼接逻辑
                    coinsResults.set(i, new ArrayList<>(coinsResults.get(i - coin)));
                    coinsResults.get(i).add(coin);
                }
            }
        }

        // 没有可行解返回空列表
        if (result[amount] == amount + 1) {
            return new ArrayList<>();
        }
        return coinsResults.get(amount);
    }

    // 测试用例
    public static void main(String[] args) {
        int[] coins = {1,2,5};
        int amount = 11;
        System.out.println(change(coins, amount)); // 输出[5,5,1]或者其他顺序的最优解，取决于硬币遍历顺序
    }
}

说明 #

• 如果你需要固定硬币组合的顺序，调整coins数组的遍历顺序即可，和Python实现的逻辑完全一致。
• 用ArrayList实现的组合复制和追加，时间复杂度和Python的列表拼接基本一致，不会额外增加算法的时间复杂度。

内容的提问来源于stack exchange，提问作者SimonNgMelbourne