322. Coin Change

自从大一大二参加完ACM之后又退出，很久没有碰算法了，工作也一年多了，重拾一下算法吧。

Coin Change 这道题算是比较基础的DP算法题了，感觉以前学的最好的就是DP了，但是最近做题目感觉全忘了，一干二净。

题目的大致意思是给出n个不同面板的硬币（每种无限多），然后给出一个总价格amount，问在如何将硬币枚数控制在最少的情况在拼出amount

662870E7-90C4-4AD7-95A5-223137594AEF.png

比较经典的DP算法

原理
DP算法主要是将复杂的问题简单化

举个例子，如果我有1，2，3个面板硬币，然后想凑出amount=4

v1次计算

我可以先从1开始计算，

1可以直接由1一个硬币得出

2-1＝1 所以呢2可以由1的枚数相加为2枚（跟自己的枚数做对比 因为是统计最少枚数，所以取少数）

3-1=2.。。。以此类推

v2次计算

之后我们拿到了2面板的硬币，直接从2..amount计算

2=2 正好枚数为1，而且比原来的2要小，所以替换为1

3-2=1 2的位置上为1，1+1<3 替换成2

。。。

v3次计算

这次拿到3，从3..amount计算

3=3 与之前一样 1<2 所以为1

4-3=1 1的枚数+3的枚数=1+1<3

65ACDEB4-EE63-4C27-BF87-A516D979B5D6.png

经过计算得出凑出amount=4的最少枚数为2

第一步当然是先初始化一个result = [Int](count:amount + 1, repeateValue:Int.max)

之后的想法有点sb，

for i in 1...amount

     for j in 0..<n

        if (a = i - coins[j]) >= 0 && result[a] != Int.max

            result[i] = min(result[i], result[a] + 1)

这个做法有个缺点就是如果amount非常大的话，计算过程也会很大，毕竟要计算 i＊j次

所以一开始就直接Time Limit Exceeded了

然后换了一种做法

直接从硬币开始循环

for coin in coins 

      for j in coin...amount

          if (a = result[j - coin]) != Int.max

             result[j] = min(result[j], a + 1)

这样就减少了相应的计算次数

func coinChange(coins: [Int], _ amount: Int) -> Int {
        if amount < 1 { return 0 }
        
        var result = [Int](count:amount + 1, repeatedValue:-1)
        result[0] = 0
        
        for coin in coins {
            if coin > amount {
                continue
            }
            for j in coin...amount {
                if result[j - coin] != -1 {
                    if result[j] == -1 {
                        result[j] = result[j - coin] + 1
                    }
                    else {
                        result[j] = min(result[j], result[j - coin] + 1)
                    }
                }
            }
        }
        
//        for i in 1..<amount + 1 {
//            for j in 0..<coins.count {
//                
//                guard let left: Int? = i - coins[j] where left >= 0 else {
//                    break
//                }
//                
//                if  result[left!] != -1 {
//                    if result[i] == -1 {
//                        result[i] = result[left!] + 1
//                    }
//                    else {
//                        result[i] = min(result[i], result[left!] + 1)
//                    }
//                }
//            }
//        }
        
        return result[amount]
    }