剑指 Offer II 103. 最少的硬币数目

动态规划。完全背包 二维数组

func coinChange(_ coins: [Int], _ amount: Int) -> Int {
        
        let len = coins.count
        let temp = Array.init(repeating: amount + 1, count:amount + 1)
        var dp = Array.init(repeating: temp, count: len + 1)
        dp[0][0] = 0

        for i in 1...len {
            let w = coins[i - 1]
            
            for j in stride(from: 0, through: amount, by: 1) {
                
                if j < w {
                    
                    dp[i][j] = dp[i - 1][j]
                    
                }else {
                    
                    dp[i][j] = min(dp[i - 1][j], 1 + dp[i][j - w])                    
                }
                
                
            }
            
            
        }                
        return dp[len][amount] == (amount + 1) ? -1 : dp[len][amount]
        
    }

转一维数组

func coinChange(_ coins: [Int], _ amount: Int) -> Int {
        
        let len = coins.count
        var dp = Array.init(repeating: amount + 1, count: amount + 1)
        dp[0] = 0

        for w in coins {
            
            for j in stride(from: w, through: amount, by: 1) {
                
                   dp[j] = min(dp[j], 1 + dp[j - w])                                    
            }
            
            
        }                
        return dp[amount] == (amount + 1) ? -1 : dp[amount]
        
    }