0%

322. Coin Change

发表于 更新于 分类于 阅读次数：
本文字数： 1.2k 阅读时长 ≈ 1 分钟

2018年5月2日 下午3:54
Coin Change - LeetCode

  1. 现在特殊情况是面值只有2。那么如果我们要求dp[1]，一元面值对应的张数，我们应该怎么给dp[1]赋值。那么对应的dp[3]用2，又应该怎么复制，这是最不可到达的。一种问题的第一个问题。
  2. 第二个问题，假如我们有两种处理方法，第一种是把它设成无限大。然后。这才这样的好处是我们使用递推公式的时候。因为递推公式要求最小值，那么我们就可以直接把这个最大值过滤掉，但是这个最大值不一定特别保险。这是他的缺点和他优点。然后第二个办法就是把它设成-1表示不可达。
  3. 现在我们考虑第二种情况，就是把这个不可达的值表示为-1，就比如说dp[3]等于-1表示dp[3]可达。那么。当dp[3]入到递推公式，求最小值之后一定就求出来就是-1。所以我们会对递推公式产生影响。
  4. 面对这个问题，我们解决方法是将递推公式拆开变成一个循环。
  5. 在每次循环中遍历各个面值，然后把一个递推公式多次执行，也就多次给dp[i]进行赋值。
  6. 在这个过程中要比大小，最终取出的跟直接求最小值递推公式是一样的。
  7. 下一个问题是你如何，何时给这个不可达设置-1的值。
  8. 我当初的想法是。找见不可到达和可到达之间的区分点。就比如说用判断啊什么的区分开。就是上面写if，下面是else句分别去执行。
  9. 老师的方法是一开始就将所有的面值对应的数量设置为-1，全部识别不可达的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    //这道题就是特殊情况比较难考虑：
    int coinChange(vector<int>& coins, int amount) {
        //初始化dp数组,初始值为-1
        std::vector<int> dp(coins.size()+1, -1);
        
        //金额0，最优解为0
        dp[0] = 0;
        for(int i = 0; i <= amount; i++){
            //循环遍历各个面值，找到dp[i]最优解
            for(int j = 0; j < coins.size(); j++){
                //i-coins[j]>=0:特殊情况面值只有2，我们要给1元赋值
                //dp[i-coins[j]]!=-1:如果前面的面值是不可到达的，那么我们不能使用它进行更新dp[i]
                if(i-coins[j]>=0 && dp[i-coins[j]]!=-1){
                    //dp[i] == -1:是dp[i]的首次赋值，dp[i] > dp[i-coins[j]] + 1：是dp[i]的寻找最优解的过程
                    if(dp[i] == -1 || dp[i] > dp[i-coins[j]] + 1){
                        dp[i] = dp[i-coins[j]] + 1;
                    }
                }
            }
        }
        return dp[amount];
    }
};