leetcode518.零钱兑换II

题目如下 数据范围

这题问能找到零的方法数量，首先可以把它当成跳格子即把amount当成目标把硬币面额当成一次可以跳的台阶数。 如下 for (int j = coins[i]; j <= amount; j++) { for (int i = 0; i < n; i++) { dp[j] += dp[j - coins[i]]; } } 这样想已经接近正确答案了 但是在跳格子中先跳1步再跳2步和先跳2步再跳1步是两种不同的方法，显然找零是不能像这样重复的，故我们要想办法排除重复计算。 即考虑将i的循环放到最外面因为我们可以得到 1 2却不能得到2 1即通过确定找零顺序排除了重复计算。 为了防止有人不能理解，我们还可以这样理解：我们只是把所有的找零序列按照面额从小到大排序，而我们这样做是不是可以枚举出所有面额从小到大的找零序列？故这样做是正确的。 注意：令人忍俊不禁的是官方说答案不会溢出，但是提交以后发现有些计算过程存在溢出所以还要验证答案是不是存在。

通过代码

class Solution { public: int change(int amount, vector<int>& coins) { int n = coins.size(); vector<int> dp(amount + 1, 0); vector<bool> is(amount + 1, false); dp[0] = 1; is[0] = true; for (int i = 0; i < n; i++) { for (int j = coins[i]; j <= amount; j++) { is[j] = is[j] || is[j - coins[i]]; } } if(!is[amount])return 0; for (int i = 0; i < n; i++) { for (int j = coins[i]; j <= amount; j++) { dp[j] += dp[j - coins[i]]; } } return dp[amount]; } };