2024 7/12 偶然在看到一部美剧《斯巴达克斯》解说，暴力美学淋漓尽致。昨晚到今天早上一口气看了八集，故10点半才到实验室，开始倦怠这种没有目的的日子，我想我需要时间来重新寻找新目标。做题吧！
1、题目描述
2、算法分析
此类问题，一眼就想到DP动态规划进行求解，难点就在怎么找到这个状态转移方程，可以使用演绎归纳。
我知道要用dp，他知道我知道要用dp，我知道他知道我知道要用dp，但问题是我该怎么dp？啊啊啊啊啊，我是sb。
题解如是说：
在“硬币找零”问题中，算法的思想如下：
- 定义状态：定义
dp[i]为组成金额i所需的最少硬币数量。这是一个一维数组，其中每个元素代表一个子问题的解。 - 初始化状态：将
dp[0]初始化为0，因为组成金额0不需要任何硬币。对于其他所有dp[i]（i > 0），初始化为一个足够大的数（例如amount +1），表示一个不可能达到的状态，这样在后续的更新过程中，只有当真正找到组成某个金额的方法时，才会更新这个值。 - 状态转移方程：对于每个金额i（从
1到amount），遍历所有硬币coins[j]。如果coins[j]小于等于当前金额i，那么可以尝试用这枚硬币加上组成剩余金额i- coins[j]所需的最少硬币数量（即dp[i - coins[j]]）来更新dp[i]。具体的更新方式是取当前dp[i]和dp[i - coins[j]] + 1中的较小值，其中+1是因为我们使用了一枚硬币coins[j]。 状态转移方程可以表示为：
dp[i] = min(dp[i], dp[i − coins[j]] + 1) for all j where coins[j] ≤ i
- 边界条件处理：在状态转移的过程中，需要特别注意边界条件。例如，当
i -coins[j]小于0时，表示剩余的金额已经小于当前硬币的面值，这种情况下不应该进行状态转移。但在本问题的设置中，由于我们是从金额1开始遍历的，并且只考虑coins[j] <= i的情况，因此这个问题自然地被避免了。 - 最终答案：算法执行完毕后，
dp[amount]就包含了组成给定金额amount所需的最少硬币数量。如果dp[amount]仍然是初始化的那个足够大的数（表示没有找到有效的组成方法），则说明无法用给定的硬币组成该金额，此时应返回-1。否则，返回dp[amount]作为答案。
3、代码
public int coinChange(int[] coins, int amount) {
// 初始化一个最大值，用于后续比较，如果dp[amount]保持为这个值，则表示无法组成该金额
int max = amount + 1;
// 创建一个dp数组，dp[i]表示组成金额i所需的最少硬币数量
// 数组长度为amount+1，因为我们需要计算从0到amount的所有金额
int[] dp = new int[amount + 1];
// 将dp数组初始化为最大值，除了dp[0]
Arrays.fill(dp, max);
// 显然，组成金额0不需要任何硬币
dp[0] = 0;
// 从金额1开始遍历到amount
for(int i = 1; i <= amount; i++){
// 遍历硬币数组
for(int j = 0; j < coins.length; j++){
// 如果当前硬币的面值小于等于当前要组成的金额
if(coins[j] <= i){
// 更新dp[i]为组成金额i所需的最少硬币数量
// 即当前硬币加上组成剩余金额所需的最少硬币数量
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
// 如果dp[amount]仍然是最初设定的最大值，说明无法组成该金额
// 否则，返回dp[amount]，即组成该金额所需的最少硬币数量
return dp[amount] > amount? -1 : dp[amount];
}
我们用案例来说明：
假设有三个硬币，分别为1、2、5。总金额为6.
初始化：
dp[0] = 0，其他数值置为amount + 1 = 7.
计算金额1：
检查硬币 1：dp[1] = min(dp[1], dp[1-1] + 1) = min(12, 0 + 1) = 1
检查硬币 2 和 5（但它们大于 1，所以在这里不更新 dp[1]）
计算金额2：
检查硬币 1：dp[2] = min(dp[2], dp[2-1] + 1) = min(7, 1 + 1) = 2
检查硬币 2：dp[2] = min(dp[2], dp[2-2] + 1) = min(2, 0 + 1) = 1（更新为更小的值）
检查硬币 5（大于 2，不更新）
计算金额3：
检查硬币 1：dp[3] = min(dp[3], dp[3-1] + 1) = min(7, 1 + 1) = 2
检查硬币 2：dp[3] = min(dp[3], dp[3-2] + 1) = min(2, 1 + 1) = 2
检查硬币 5（大于 3，不更新）
计算金额4：
检查硬币 1：dp[4] = min(dp[4], dp[4-1] + 1) = min(7, 2 + 1) = 3
检查硬币 2：dp[4] = min(dp[4], dp[4-2] + 1) = min(3, 1 + 1) = 2（更新为更小的值）
检查硬币 5（大于 3，不更新）
计算金额5：
检查硬币 1：dp[5] = min(dp[5], dp[5-1] + 1) = min(7, 2 + 1) = 3
检查硬币 2：dp[5] = min(dp[5], dp[5-2] + 1) = min(3, 2 + 1) = 3
检查硬币 5：dp[5] = min(dp[5], dp[5-5] + 1) = min(3, 0 + 1) = 1（更新为更小的值）
计算金额6：
检查硬币 1：dp[6] = min(dp[6], dp[6-1] + 1) = min(7, 1 + 1) = 2
检查硬币 2：dp[6] = min(dp[6], dp[6-2] + 1) = min(2, 2 + 1) = 2
检查硬币 5：dp[6] = min(dp[6], dp[6-5] + 1) = min(2, 1 + 1) = 2
最终返回dp[6]即为我们需要的最小硬币数2。
4、复杂度分析
- 时间复杂度：
O(Sn)，其中 S 是金额，n 是面额数。我们一共需要计算 O(S) 个状态，S为题目所给的总金额。对于每个状态，每次需要枚举 n 个面额来转移状态，所以一共需要 O(Sn) 的时间复杂度。 - 空间复杂度：
O(S)。数组 dp 需要开长度为总金额 S 的空间。
okok拜拜啦！外卖刚好到了，该吃饭看会电影了！
