动态规划简称DP，是一种求解最优化问题的一种常用策略，它会尝试每一种选择，来获取解决问题的最优解。
我们下面通过之前在贪心策略里面的提到的找零钱的例子，来探讨动态规划。我们先来回顾下找零钱这个问题。
- 假设有25分、20分、5分、1分的硬币，现要找给客户41分的零钱，如何办到硬币个数最少？
在 贪心策略文章中，我们探讨了该问题使用贪心策略得到的解为需5枚硬币，并非最优解。
分析
我们假设dp(n)是凑到 n 分需要的最少硬币数，分析如下：
- 如果第1次选择了 25 分的硬币，那么 dp(n) = dp(n - 25) + 1。
- 如果第1次选择了 20 分的硬币，那么 dp(n) = dp(n - 20) + 1。
- 如果第1次选择了5分的硬币，那么 dp(n) = dp(n - 5) + 1。
- 如果第1次选择了1分的硬币，那么 dp(n) = dp(n - 1) + 1
综上所述 dp(n) = min{ dp(n - 25), dp(n - 20), dp(n - 5), dp(n - 1)} + 1
实现
按照以上思路，我们可以先用 递归的思想来实现，我们新建一个类 DynamicPrograming
class DynamicProgramming {
static let changes = [25, 20, 5, 1]
// coin Change
static func coinChange(_ num: Int) -> Int{ // 1
if num <= 0 {
return Int.max // 2
}
for change in changes {
if num == change {
return 1 // 3
}
}
let one = coinChange(num - 25) //4
let two = coinChange(num - 20)
let three = coinChange(num - 5)
let four = coinChange(num - 1)
let five = min(one, two)
let six = min(three, four)
return min(five, six) + 1 // 5
}
}
- 1，
coinChange(:)->Int方法表示需要对 n 元进行找零需要的最少硬币个数。 - 2，因为我们要取最小值，当需要找零的数值小于0时，此时我们返回最大的整数。
- 3，当需找零的值和零钱的面值相等，此时，需要的最小零钱个数为1。
- 4，分别计算出
num - 25、num - 20、num - 5、num - 1所需的最小零钱个数。 - 5， 返回 4中方案的最小值 + 1。
这样的话，我们就可以求出找零时，需要的最小零钱个数。但是，上面通过递归的方式计算，有可能会存在一些重复计算，假设对4元进行找零，我们会多次 计算 coinChange(1)。我们可以进行记忆化搜索，将计算结果保存起来，当需要再次计算的时候，直接将值返回即可。我们可以使用 字典 进行保存，也可以使用数组进行保存。在这里，我们先使用字典进行保存
static func coinChangeTwo(_ num: Int) -> Int {
if num <= 0 {
return Int.max
}
for change in changes {
if change == num {
return 1
}
}
if dpDic[num - 25] == nil {
dpDic[num - 25] = coinChange(num - 25)
}
if dpDic[num - 20] == nil {
dpDic[num - 20] = coinChange(num - 20)
}
if dpDic[num - 5] == nil {
dpDic[num - 5] = coinChange(num - 5)
}
if dpDic[num - 1] == nil {
dpDic[num - 1] = coinChange(num - 1)
}
let one = dpDic[num - 25] ?? Int.max
let two = dpDic[num - 20] ?? Int.max
let three = dpDic[num - 5] ?? Int.max
let four = dpDic[num - 1] ?? Int.max
let minOne = min(one, two )
let minTwo = min(three, four)
return min(minOne, minTwo) + 1
}
我们进一步分析该代码，如果我们想求出 dp(41)：对41元进行找零，所需的最少硬币个数,我们需要 先求出 dp(16)、dp(21)、dp(36)、dp(40)，由此，我们可以看出，我们可以先求 dp(1)、dp(2)、dp(3)直到 dp(n)。自底而上的递推出每个零钱方案。根据我们之前分析的结果 dp(n) = min{ dp(n - 25), dp(n - 20), dp(n - 5), dp(n - 1)} + 1，我们可以
var dp = Array.init(repeating: 0, count: num + 1) // 1
for i in 1...num {
var minValue = Int.max
minValue = min(dp[i - 1], minValue)
minValue = min(dp[i - 5], minValue)
minValue = min(dp[i - 20], minValue)
minValue = min(dp[i - 25], minValue) // 2
dp[i] = minValue + 1 // 3
}
- 1，初始化一个长度为 num + 1的数组，用来存储dp(n)的值。
- 2，求出dp[i]的值。
- 3，对dp[i]进行存储。
为防止数组越界，我们额外需要增加一些判断
static func coinsChangeThree(_ num: Int) -> Int {
if num <= 0 {
return Int.max
}
var dp = Array.init(repeating: 0, count: num + 1)
for i in 1...num {
var minValue = Int.max
// dp[index] = min {dp[i-25], dp[i-20], dp[i-5], dp[i-1]} + 1
if i >= 1 {
minValue = min(dp[i - 1], minValue)
}
if i >= 5 {
minValue = min(dp[i - 5], minValue)
}
if i >= 20 {
minValue = min(dp[i - 20], minValue)
}
if i >= 25 {
minValue = min(dp[i - 25], minValue)
}
dp[i] = minValue + 1
}
return dp[num]
}
如上所示，我们先算出 dp(1) = 1,然后计算 dp(2) = dp(1) + 1 = 2,然后在由 dp（2）推到出dp(3)，最后，推导出 dp(n)。我们将所有的找零需要的最少硬币数都存在了数组里面。
从这个过程中，我们可以看出，我们首先是要找到问题状态转移方程即上面的dp(n) = min{ dp(n - 25), dp(n - 20), dp(n - 5), dp(n - 1)} + 1，通过这个状态转移方程，我们可以使用递归的方式实现，如果递归算法中有许多的重复计算，我们采用记忆化搜索来避免重复计算。最后，采用自底而上的递推来避免递归调用。
网友评论