动态规划(一)

动态规划(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}$
代码:

//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
}

递归树:

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})$。

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

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

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

代码:

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]枚硬币。

代码:

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
如果觉得我的文章对你有用,请随意赞赏