动态规划问题

动态规划（英语：Dynamic programming，简称DP）： 通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

概述

动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间。

动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解（对有些问题这个要求并不能完全满足，故有时需要引入一定的近似）。简单地说，问题能够分解成子问题来解决。

适用情况

1. 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
2. 无后效性。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
3. 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

实例

1、斐波那契数列（Fibonacci polynomial) :（第3点适用情况：相似子问题被计算多次）
【1、1、2、3、5、8、13、21、34】

// 递归实现
func fibonacci(n: Int) -> Int {
    if (n == 0 || n == 1) {
        return n
    }
    return fibonacci(n: n - 1) + fibonacci(n: n - 2)
}

// 动态规划实现: 时间复杂度：O(n)
var dict: [Int : Int] = [0:0 , 1:1]
func fib(_ n: Int) -> Int {
    print("fib:[" + "\(n)" + "]")
    if dict[n] == nil {
        dict[n] = fib(n - 1) + fib(n - 2)
    }
    return dict[n]!
}

2、背包问题：
【解整数背包问题】：

背包问题 .png

动态规划解法.png

func maxofValue(x: Int, y: Int) -> Int {
    return x >= y ? x : y
}

func maxValueOfBag(max: Int) -> Int {
    let weights: [Int] = [3,5,20,1,3,5,1,6,6]
    let values: [Int] =  [4,7,1,1,1,8,5,5,4]
    var array = [[Int]](repeating:[Int](repeating: 0, count: max) , count: weights.count)

    for i in 1 ... weights.count - 1  {
        for j in 1 ... max - 1 {
            if weights[i] > j {
                array[i][j] = array[i - 1][j]
            } else {
                array[i][j] = maxofValue(x: array[i - 1][j], y: values[i] + array[i - 1][j - weights[i]])
            }
        }
    }
    for i in 0 ... weights.count - 1 {
        print(array[i])
    }
    return array[weights.count - 1][max - 1]
}

let v = maxValueOfBag(max: 15)
print("结果：" + "\(v)")