【算法】动态规划

Author： Rehtt
发布时间：April 16, 2021
4037 views
No comments
3134 words
Categories：算法

# 动态规划（一）

动态规划（Dynamic Programming）其实是运筹学中一种优化方法，动态规划一般就是求最值，比如最少次数、最短距离等。

求解动态规划的核心问题其实就是 `穷举`。因为要求出问题的最值，所以需要穷举出每一种答案找到最值。

当存在重复子问题时，如果是暴力穷举就会重复计算，导致效率低下。而优化的方法是建立“备忘录”或“DP数组”，避免重复计算。

## 例题：凑零钱问题

现有 `k`种面额的硬币，面值分别 `c1,c2,...,ck`，每种硬币的数量是无限的，现在有一个目标金额 `amount`，问**最少**需要多少枚硬币可以凑到这个金额，如果凑不出就返回 -1。

假如现有 `k=3`，面额为 `1,2,5`的三种硬币，目标金额 `amount = 11`，则最少需要3枚硬币凑出，即 `5 + 5 + 1 = 11`。

### 子问题

子问题是原问题的划分，例如求f(8)需要求出f(7)，求f(7)需要求出f(6)以此类推，f(8)的子问题是f(7)，f(7)的子问题是f(6)。

凑零钱问题中，求目标 `11`最少硬币数量，子问题就是 `10`最少硬币数量，再次划分就是 `9`最少硬币数量以此类推。

### 最优子结构

首先这是一个的动态规划问题，因为它具有“最优子结构”。“最优子结构”的子问题间必须相互独立、互不干扰。

比如：a = b + c，求a的最大值就需要求b和c的最大值，b和c互不干扰，因此这符合“最优子结构”。如果b与c互相干扰，比如增长b那么c就减小，那么就不是“最优子结构”。

凑零钱的问题中，各硬币的数量之间没有限制，硬币总数也是无限的。子问题之间是相互独立的。

### 状态转移

动态规划的核心是穷举最值，只有列举出正确的“状态转移方程”才能正确穷举。

思考确定状态转移方程：

1. **确定 base case（最简情况）**。在凑零钱中当`amount=0`时就返回0，表示不需要硬币了。
2. **确定“状态”，也是原问题和子问题的变量**。因为硬币是无限的，硬币的面额也是确定的，当目标不断向base case靠近，所以唯一的“状态”就是目标`amount`。
3. **确定“选择”，也就是导致“状态”产生“变化”的行为**。目标`amount`之所以会变，是因为“选择”了硬币。当选择了面额为1的硬币，那么目标`amount=11`就变为了`amount=10`，所以硬币的面额就是选择。
4. **明确dp函数/数组的定义**。接下来会先展示递归，所以使用dp函数，dp函数中参数就是状态转移的变量，也就是“状态”，函数返回值就是计算的量。

### 一、暴力递归解法

这道题中当目标金额为0 时，所需要的硬币为0；小于0时，无解，返回 -1。
状态转移方程：

$dp(n)=\begin{cases}
0,n=0
\\ amount+1,n<0
\\ min\{dp(n-coin)+1|coin \in coins)\},n>0
\end{cases}$
代码：

```go
//coins为硬币面额，amount为目标金额
//coins=[1,2,5]，amount=11
func dp(coins []int,amount int)int{
    if n==0 {return 0}  // base case
    if n<0 {return -1}
    num:=amount+1   //因为凑出硬币的数量永远也不可能大于目标金额，所以amount+1表示无穷大。而求最小值，所以初始化无穷大。
    //“选择”
    for _,coin:=range coins{
        sub:=dp(coins,amount - coin)
        if sub == -1{continue}  //子问题无解，跳过
        //min()
        if num > 1+sub{
            num = 1+sub
        }
    }
    if num==amount+1{   //没有凑出
        return -1
    }
    return num
}
```

递归树：

```mermaid
graph TB
a((11))--1-->b((10))
a--2-->c((9))-->c0((...))
a--5-->d((6))
b--1-->b0((9))
b--2-->b1((8))-->b10((...))
b--5-->b2((5))-->b20((...))
b0--1-->b00((8))
b0--2-->b01((7))
b0--5-->b02((4))
d--1-->d0((5))-->d00((...))
d--2-->d1((4))
d--5-->d2((1))-->d20((...))
d1--1-->d10((3))
d1--2-->d11((2))
d1--5-->d12(("-1"))
```

通过递归树可以看到，存在 `amount`相同的重复子问题，从而导致算法效率低下。

***递归算法时间复杂度 = 子问题总数时间复杂度 x 每个子问题时间复杂度***

在此暴力递归中，子问题总数时间复杂度为$O(n^{k})$，每个子问题时间复杂度为$O(k)$。因此本暴力递归的中时间复杂度为$O(kn^{k})$。

### 二、带“备忘录”的递归解法

从上述的暴力递归树中可以看出，存在许多重复的子问题，这些重复的子问题就是导致算法效率低的主要原因。那么针对这个问题，我们可以建立一个“备忘录”来存储每个子问题计算的结果，在计算子问题之前先查询是有结果存在“备忘录”中，如果存在就直接使用“备忘录”中的值而不再去计算。

*一般“备忘录”可以使用数组或哈希表来建立。*

代码：

```go
var tab []int   //备忘录
func dp(coins []int,amount int)int{
    //初始化备忘录
    if tab == nil{tab=make([]int,len(coins))}

if n==0 {return 0}
    if n<0 {return -1}
    num:=amount+1   
    for _,coin:=range coins{
        i := amount - coin
        //查表，若结果不存在的话就进行计算
        if tab[i]==0{
            tab[i] = dp(coins,i)
        }
        if tab[i] == -1{continue}
        //min()
        if num > 1 + tab[i]{
            num = 1 + tab[i]
        }
    }
    if num==amount+1{
        return -1
    }
    return num
}
```

带有“备忘录”的递归就解决了重复子问题冗余的问题,因此子问题的个数不会超过目标金额$n$，因此带“备忘录”的递归的总时间复杂度为$O(kn)$。

### 三、dp数组迭代解法

以上递归都是自顶向下的解法，“状态”`amount`的变化为：11、10、...、0
而dp数组迭代则是自底向上的解法，“状态”`amount`的变化为：1、2、...、11

dp数组的定义：当目标金额为 `n`时，最多需要 `dp[n]`枚硬币。

代码：

```go
func coinChange(coins []int,amount int)int{
    //创建dp数组，长度为amount+1
    dp := make([]int,amount+1)

//初始化dp数组，除dp[0]以外都赋值amount+1
    //以dp数组下标为各“状态”目标金额。
    //当“状态”为0时，结果为零，因此dp[0]=0。base case
    //除0其他以外，都赋值amount+1。amount+1为硬币永远也达不到的数量，本题求最少硬币数量，因此amount+1表示无穷大。
    for i:=1;i<amount+1;i++{
        dp[i] = amount+1
    }
    //变量所有状态取值
    for i:=0;i<len(dp);i++{
        //寻找最少硬币数量
        for _,coin := range coins{
            // 子问题无解，跳过
            if i-coin<0 {
                continue
            }
            //min()
            if dp[i] > 1+dp[i-coin]{
                dp[i] = 1+dp[i-coin]
            }
        }
    }
    //结果为amount+1“无穷大”为无解返回-1
    if dp[amount] == amount+1{
        return -1
    }
    return dp[amount]
}
```

Last modification：April 16, 2021