老师, 能不能把所有可能的组合输出来, 而不是仅仅输出一个3, 想了下代码好像比较麻烦

当amount = 2147483647时，视频中的代码是有问题的，很遗憾LeetCode并没有这样的TestCase

白板有问题吧。min{dp[i - coinsp[j]} + 1， 大括号里面就一个元素，求谁跟谁的最小值啊。

PHP 的两种解法 public $min = PHP_INT_MAX; /** * dfs 解法 */ function coinChange1($coins, $amount) { if (empty($coins)) return -1; if ($amount == 0) return 0; sort($coins); if ($amount < $coins[0]) return -1; $sum = 0; $this->dfs($coins, $amount, $sum, count($coins) - 1); return $this->min === PHP_INT_MAX ? -1 : $this->min; } function dfs($coins, $amount, $sum, $index) { if ($index < 0 || ($sum + $amount / $coins[$index] >= $this->min)) return; if ($amount == 0) { $this->min = min($this->min, $sum); return; } for ($i = $index; $i >= 0; --$i) { if ($amount < $coins[$i]) continue; $this->dfs($coins, $amount - $coins[$i], $sum + 1, $i); } } /** * 动态规划 */ function coinChange($coins, $amount) { $dp = array_fill(1, $amount + 1, $amount + 1); $dp[0] = 0; for ($i = 1; $i <= $amount; $i++) { // for ($j = 0; $j < count($coins); $j++) { // if ($coins[$j] <= $i) { // $dp[$i] = min($dp[$i], $dp[$i - $coins[$j]] + 1); // } // } foreach ($coins as $coin) { if ($coin <= $i) { $dp[$i] = min($dp[$i], $dp[$i - $coin] + 1); } } } return $dp[$amount] > $amount ? -1 : $dp[$amount]; }

return 里的 -1 if dp[amount] > amount 应该不能改为 dp[amount] == amount + 1 。因为递推计算时可能有的dp元素变为amount + 2 或更大

茶艺师学编程： 322. 零钱兑换 class Solution: def coinChange(self, coins: List[int], amount: int) -> int: MAX=float('inf') dp=[0]+[MAX for i in range(amount)] for i in range(1,amount+1): for c in coins: if i-c>=0: dp[i]=min(dp[i],dp[i-c]) dp[i]+=1 if dp[-1]==MAX: return -1 else: return dp[-1]

虽然题目限定了，0 <= amount <= 104，但当amount 为INT_MAX时会溢出

暴力的时间复杂度度应该是n^n吧，第一的n是amount,第二个n是len(coins)

1.复杂度O（x*n） 2.dp的两种题型：序列“选择”最优问题 序列“排列”（可重复）最优

这个题目是要求出最长子序列的长度，所以二分查找法适用，如果要求出内容，是用动态规划。