一、斐波那契数列

/// 1. 爬楼梯 : 一次只能前进 1 或 2
/// - Parameter step: 台阶数
/// - Returns:
fileprivate func climbStairs(step:Int) -> Int {
    var first,second,res : Int
    if(step <= 0){
        return 0 // 处理异常数据
    }else if(step == 1){
        return 1 // 1阶 固定值
    }else if(step == 2){
        return 2 // 2阶 固定值
    }
    first = 1;second = 2;res = 3 // 初始化变量
    for _ in 3...step {
        // 核心： 到达第n阶只有两种可能， 第n-1阶往前1步，第n-2阶往前2步，所以第n阶的不同方法为第n-1阶与第n-2阶的方法和
        res = first + second
        first = second
        second = res
    }
    return res
}


/// 2.斐波那契数：0,1,1,2,3... 当前数为前两个数之和
/// - Parameter n: <#step description#>
/// - Returns: <#description#>
fileprivate func fib(_ n: Int) -> Int {
    var first,second,res : Int
    if(n <= 0){
        return 0
    }else if(n == 1){
        return 1
    }else if(n == 2){
        return 1
    }
    first = 1;second = 1;res = 2 // 初始化变量
    for _ in 3...n {
        res = first + second
        first = second
        second = res
    }
    return res
}

/// 3.泰波那契数：0,1,1,2,4... 当前数为前n个数之和（这里的n = 3）
/// - Parameter n: <#step description#>
/// - Returns: <#description#>
fileprivate func fib_3(_ n: Int) -> Int {
    var first,second,third,res : Int
    if(n <= 0){
        return 0
    }else if(n == 1){
        return 1
    }else if(n == 2){
        return 1
    }else if(n == 3){
        return 2
    }
    first = 1;second = 1;third = 2;res = 4 // 初始化变量
    for _ in 4...n {
        res = first + second + third
        first = second
        second = third
        third = res
    }
    return res
}

/// 4. 最小花费爬楼梯：每次向前1,2，每节楼梯都有自己的花费
/// - Parameter step: 台阶数数组，元素为每阶花费
/// - Returns: <#description#>
fileprivate func minimumCostClimbStairs(step:[Int]) -> Int{
    if(step.count == 0){
        return 0
    }else if(step.count == 1){
        return 0
    }else if(step.count == 2){
        return min(step[0], step[1])
    }
    let first = step[0]
    let second = step[1]
    /**
     核心：到达n阶有两种方式，从n-1前进1步，或从n-2前进两步
     那么只要取这两种方式的最小值：Min(到n-1的总开销和n-1当前开销 : 到n-2的总开销+n-2的当前开销)
     */
    var sumN_2:Int = 0 // 到n-2的花费
    var sumN_1:Int = 0 // 到n-1的花费
    var cosN_2:Int = first // n-2的花费
    var cosN_1:Int = second // n-1的花费

    for i in 3...step.count {
        let cosN = step[i - 1]
        let sumN = min(cosN_1 + sumN_1, cosN_2 + sumN_2)
        // 完成最后一次交换
        cosN_2 = cosN_1
        sumN_2 = sumN_1
        cosN_1 = cosN
        sumN_1 = sumN
    }
    // 计算最后的结果时，要加上cos
    return min(sumN_2 + cosN_2, sumN_1 + cosN_1);
}

/// 5.最大花费爬楼梯: 增加条件 1.不可以连续爬1阶（相邻），比如 7-8  2.爬不做限制
/// - Parameter step: <#step description#>
/// - Returns: <#description#>
fileprivate func maxCostClimbStairs(step:[Int]) -> Int{
    // 隐藏条件，达到第n阶有三种情况，max(n-1的总花费+n-1阶，n-2的总花费+n-2阶,n-4的总花费+(n-4)阶+n-1阶)
    var sum_1 = 0
    var sum_2 = 0
    var sum_3 = 0
    var sum_4 = 0
    if(step.count == 0){
        return 0
    }else if(step.count == 1){
        sum_4 = step[0]
        return sum_4;
    }else if(step.count == 2){
        sum_3 = max(step[0], step[1]);
        return sum_3;
    }else if(step.count == 3){
        sum_2 = max(step[1], step[0] + step[2]);
        return sum_2;
    }else if(step.count == 4){
        sum_1 = max(step[0] + step[2],step[0] + step[3],step[1] + step[3])
        return sum_1
    }
    
    sum_1 = max(step[0] + step[2],step[0] + step[3],step[1] + step[3])
    sum_2 = max(step[1], step[0] + step[2]);
    sum_3 = max(step[0], step[1]);
    sum_4 = step[0]
    
    var res = 0;
    for i in 4...step.count-1 {
        // 计算两种情况，当前与n-2，当前与n-3,因为不能连续，所以不能与 n-1比
        res = max(sum_2 + step[i], sum_3 + step[i])
        // 其他平移向后
        sum_4 = sum_3
        sum_3 = sum_2
        sum_2 = sum_1
        // 最后替换sum_1
        sum_1 = res;
    }
    
    return max(sum_1, sum_2, sum_3, sum_4)
}

/// 6.删除并添加数，条件：整数数组、元素无序且可能重复，删除一个数后，它的+1、-1将被忽略。先排序、转化为字典，key=值，value=值*重复次数，然后分段处理，不连续的数直接添加，连续的数转化为爬楼梯
/// - Parameter nums: <#nums description#>
/// - Returns: <#description#>
fileprivate func deleteAndEarn(_ nums: [Int]) -> Int {
    // 将数组排序
    let sorts = nums.sorted(by: <)
    // 整合新数组，value对应的是 值 * 出现次数
    var newValues = [Int]()
    var newKeys = [Int]()
    var unit = 0;
    var currentNum = 0;
    for num in sorts {
        if(newKeys.contains(num) == false){
            newKeys.append(num)
        }
        // current初始化
        if(currentNum == 0){
            currentNum = num
        }
        // 如果num在重复
        if(currentNum == num){
            unit += num
        }else {
            // 如果num不再重复，说明是新的元素
            newValues.append(unit)
            unit = num
            currentNum = num
        }
    }
    newValues.append(unit)

    // 遍历，找梯子ladder，如果没有梯子序列，直接可以加，有梯子，就走打家劫舍的方法
    var ladderArr = [Int]()
    var res = 0
    var tempKey = 0
    var tempKeyIndex = 0
    for keyIndex in newKeys.indices {
        let key = newKeys[keyIndex]
        // 初始化
        if(tempKey == 0){
            tempKey = key
            tempKeyIndex = keyIndex
        }else {
            // 如果key与tempNum形成梯子，那么存储到梯子数组
            if(key == tempKey + 1){
                ladderArr.append(tempKeyIndex)
            }else {
                // 梯子结束
                ladderArr.append(tempKeyIndex)
                var paramArr = [Int]()
                for param in ladderArr {
                    paramArr.append(newValues[param])
                }
                res += maxCostClimbStairs(step: paramArr)
                ladderArr.removeAll()
                tempKey = 0
                tempKeyIndex = 0
            }
            tempKey = key
            tempKeyIndex = keyIndex
        }
    }
    if(tempKey != 0){
        ladderArr.append(tempKeyIndex)
    }
    if(ladderArr.count > 0){
        var paramArr = [Int]()
        for param in ladderArr {
            paramArr.append(newValues[param])
        }
        res += maxCostClimbStairs(step: paramArr)
        ladderArr.removeAll()
    }

    return res
}

/**
 fileprivate func maxCostClimbStairs(step: [Int]) -> Int {
     var dp = [Int](repeating: 0, count: step.count + 1)
     if step.count == 0 {
         return 0
     }
     
     for i in 0..<step.count {
         dp[i + 1] = max(dp[i], (i >= 2 ? dp[i - 1] : 0) + step[i])
     }
     
     return dp[step.count]
 }

 fileprivate func deleteAndEarn(_ nums: [Int]) -> Int {
     if nums.isEmpty {
         return 0
     }
     
     let maxValue = nums.max()!
     var values = [Int](repeating: 0, count: maxValue + 1)
     
     for num in nums {
         values[num] += num
     }
     
     return maxCostClimbStairs(step: values)
 }
 */