动态规划(一)
动态规划(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就减小,那么就不是“最优子结构”。
凑零钱的问题中,各硬币的数量之间没有限制,硬币总数也是无限的。子问题之间是相互独立的。
状态转移
动态规划的核心是穷举最值,只有列举出正确的“状态转移方程”才能正确穷举。
思考确定状态转移方程:
- 确定 base case(最简情况)。在凑零钱中当
amount=0
时就返回0,表示不需要硬币了。 - 确定“状态”,也是原问题和子问题的变量。因为硬币是无限的,硬币的面额也是确定的,当目标不断向base case靠近,所以唯一的“状态”就是目标
amount
。 - 确定“选择”,也就是导致“状态”产生“变化”的行为。目标
amount
之所以会变,是因为“选择”了硬币。当选择了面额为1的硬币,那么目标amount=11
就变为了amount=10
,所以硬币的面额就是选择。 - 明确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]
}