比如说，你的原问题是考出最高的总成绩，那么你的子问题就是要把语文考到最高，数学考到最高...... 为了每门课考到最高，你要把每门课相应的选择题分数拿到最高，填空题分数拿到最高...... 当然，最终就是你每门课都是满分，这就是最高的总成绩。
得到了正确的结果：最高的总成绩就是总分。因为这个过程符合最优子结构，“每门科目考到最高”这些子问题是互相独立，互不干扰的。
但是，如果加一个条件：你的语文成绩和数学成绩会互相制约，此消彼长。这样的话，显然你能考到的最高总成绩就达不到总分了，按刚才那个思路就会得到错误的结果。因为子问题并不独立，语文数学成绩无法同时最优，所以最优子结构被破坏。
回到凑零钱问题，显然子问题之间没有相互制约，而是互相独立的。所以这个状态转移方程是可以得到正确答案的。
int coinChange(vector<int>& coins, int amount) { if (amount == 0) return 0; int ans = INT_MAX; for (int coin : coins) { // 金额不可达 if (amount - coin < 0) continue; int subProb = coinChange(coins, amount - coin); // 子问题无解 if (subProb == -1) continue; ans = min(ans, subProb + 1); } return ans == INT_MAX ? -1 : ans; }画出递归树：
时间复杂度分析：子问题总数 x 每个子问题的时间。子问题总数为递归树节点个数，这个比较难看出来，是 O(n^k)，总之是指数级别的。每个子问题中含有一个 for 循环，复杂度为 O(k)。所以总时间复杂度为 O(k*n^k)，指数级别。
二、带备忘录的递归算法
int coinChange(vector<int>& coins, int amount) { // 备忘录初始化为 -2 vector<int> memo(amount + 1, -2); return helper(coins, amount, memo); } int helper(vector<int>& coins, int amount, vector<int>& memo) { if (amount == 0) return 0; if (memo[amount] != -2) return memo[amount]; int ans = INT_MAX; for (int coin : coins) { // 金额不可达 if (amount - coin < 0) continue; int subProb = helper(coins, amount - coin, memo); // 子问题无解 if (subProb == -1) continue; ans = min(ans, subProb + 1); } // 记录本轮答案 memo[amount] = (ans == INT_MAX) ? -1 : ans; return memo[amount]; }不画图了，很显然「备忘录」大大减小了子问题数目，完全消除了子问题的冗余，所以子问题总数不会超过金额数 n，即子问题数目为 O(n)。处理一个子问题的时间不变，仍是 O(k)，所以总的时间复杂度是 O(kn)。
三、动态规划
int coinChange(vector<int>& coins, int amount) { vector<int> dp(amount + 1, INT_MAX); dp[0] = 0; for (int i = 0; i < dp.size(); i++) { // 内层 for 在求所有子问题 + 1 的最小值 for (int coin : coins) { if (i - coin < 0) continue; dp[i] = min(dp[i], 1 + dp[i - coin]); } } return dp[amount] == INT_MAX ? -1 : dp[amount]; }最后总结
如果你不太了解动态规划，还能看到这里，真得给你鼓掌，相信你已经掌握了这个算法的设计技巧。
计算机解决问题其实没有任何奇技淫巧，它唯一的解决办法就是穷举，穷举所有可能性。算法设计无非就是先思考“如何穷举”，然后再追求“如何聪明地穷举”。
列出动态转移方程，就是在解决“如何穷举”的问题。之所以说它难，一是因为很多穷举需要递归实现，二是因为有的问题本身的解空间复杂，不那么容易穷举完整。
备忘录、DP table 就是在追求“如何聪明地穷举”。用空间换时间的思路，是降低时间复杂度的不二法门，除此之外，试问，还能玩出啥花活？