内容简介:本文一共分三部分:动态规划(动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能解决全局最优解。
本文一共分三部分:
- 什么是动态规划?
- 平时编程过程中,哪些场景适用于适用动态规划?
- 动态规划代码怎么写?
什么是动态规划?
动态规划( dynamic programming
,简称 DP
), 是求解决策过程最优化的数学方法,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。动态规划是一种利用空间换时间来求解最优解的的方法,一般在编程中的时间复杂度会少于常规解法(如暴力解法,回溯算法)。
适用情况
动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能解决全局最优解。
- 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子机构性质(即满足最优化原理)。最优子结构性质为动态规划算法解决问题提供了重要线索。
- 无后效性。即子问题的解一旦确定,就不再改变,不受在这之后、包含它的更大问题的求解决策影响。
- 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次,动态规划算法正是利用了这些子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简单的查看一下结果,从而获得较高的效率。
动态规划代码怎么写?
下面看几个例子>
爬楼梯问题
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
解法一:暴力解法
在暴力解法中,我们将会把所有可能爬的楼梯阶数进行组合,也就是1和2. 而在每一步中我们都会递归调用原函数模拟爬1阶和2阶的情形,并返回两个函数的返回值之和。
// 其中i定义了当前阶数,n定义的是目标阶数 climbStairs(i, n) = climbStairs(i+1, n) + climbStairs(i+2, n) 复制代码
// Swift实现算法 func climbStairs(_ n: Int) -> Int { return climbStairs(0, n: n) } func climbStairs(_ i: Int, n: Int) -> Int { if i > n { return 0 } if i == n { return 1 } return climbStairs(i + 1, n: n) + climbStairs(i + 2, n: n) } 复制代码
复杂度分析:
-
时间复杂度:O(2^n)。树形递归的大小为2^n
n = 5时,递归树是这样的
- 空间复杂度:O(n)。递归树的深度可以达到n。
解法二:记忆化递归
使用暴力法求解,每一步计算结果都出现了冗余。另一种思路是,我们可以把每一步的结果存储在memo数组之中,每当函数再次调用,我们就直接从memo数组返回结果。 在memo数组的帮助下,我们得到一个修复的递归树,其大小减小到n。
func climbStairs(_ n: Int) -> Int { var memo = Array(repeating: 0, count: n) return climbStairs(0, n: n, memo: &memo) } func climbStairs(_ i: Int, n: Int, memo: inout Array<Int>) -> Int { if i > n { return 0 } if i == n { return 1 } if memo[i] > 0 { return memo[i] } memo[i] = climbStairs(i + 1, n: n, memo: &memo) + climbStairs(i + 2, n: n, memo: &memo); return memo[i] } 复制代码
复杂度分析:
- 时间复杂度:O(n)。树形递归的大小减小到n
- 空间复杂度:O(n)。递归树的深度达到n
解法三:动态规划
不难发现,这问题可以被分解成一些包含最优子结构的子问题,即它的最优解可以从其子问题的最优解来有效的构建,我们可以使用动态规划来解决这一问题。
第i阶可以由以下两种方法得到:
- 在第
(i-1)
阶向后爬一阶。 - 在第
(i-2)
阶向后爬二阶。 所以,到达第i阶的方法总数就是(i-1)
阶和(i-2)
阶方法数之和。
令dp[i]表示能到达第i阶的方法总数: dp[i] = dp[i-1] + dp[i-2]
func climbStairs(_ n: Int) -> Int { if n == 1 { return 1 } var dp = Array(repeating: 0, count: n+1) dp[1] = 1 dp[2] = 2 for i in 3...n { dp[i] = dp[i-1] + dp[i-2] } return dp[n] } 复制代码
通过这个例子,我们可以总结以下,动态规划的思考过程: 动态规划的思考过程可以总结为: 大事化小,小事化了 。
大事化小
一个较大的问题,通过找到与子问题的重叠,把复杂的问题划分为多个小问题,也成为状态转移。
小事化了
小问题的解决通常是通过初始化,直接计算结果得到;
具体的步骤:
- 将大问题分解为子问题
- 确定状态表示
- 确定状态转移
- 考虑初始状态和边界情况
一些动态规划的例子
零钱凑整
如果我们有面值为1元、3元和5元的硬币若干枚,如何用最少的硬币凑够11元?
- 将大问题分解为子问题:因为由1、3、5元硬币组成11元情况比较多,用暴力法穷举出所有情况比较复杂,我们可以把这个问题分解成若干个子问题,用dp[i]表示凑够i元钱所需的硬币数量,dp[i] = min{dp[i-1]+1, dp[i-3]+1, dp[1-5]+1}
- 状态表示:dp[i]
- 状态转移方程:伪代码表示
if i < 3 dp[i] = dp[i-1] + 1 else if i >= 5 dp[i] = min{dp[i-1]+1, dp[i-3]+1, dp[1-5]+1} else dp[i] = min{dp[i-1]+1, dp[i-3]+1} 复制代码
- 考虑初始状态和边界情况 当
i = 0
时,0个硬币即可 当i = 1, i = 3, i = 5
时,只需要1个硬币即是最优解
代码如下:
func countMoney(_ n: Int) -> Int { if n == 0 { return 0 } var dp = Array(repeating: 0, count: n+1) dp[1] = 1 dp[3] = 1 dp[5] = 1 for i in 1...n { if i < 3 { dp[i] = dp[i-1] + 1 } else if i >= 5 { dp[i] = min(dp[i-1] + 1, dp[i-3]+1, dp[i-5]+1) } else { dp[i] = min(dp[i-1] + 1, dp[i-3] + 1) } } return dp[n] } 复制代码
接下来,我们再看一到题
背包问题
话说有一哥们去森林里玩发现了一堆宝石,他数了数,一共有n个。 但他身上能装宝石的就只有一个背包,背包的容量为C。这哥们把n个宝石排成一排并编上号: 0,1,2,…,n-1。第i个宝石对应的体积和价值分别为 V[i]
( V
代表 volume
)和 W[i]
( W
代表 worth
)。排好后这哥们开始思考: 背包总共也就只能装下体积为C的东西,那我要装下哪些宝石才能让我获得最大的利益呢?
按照上面的步骤对问题进行分析: 我们定义一个函数 F(i, j)
,表示能够装的宝石的最大价值, i
表示有的宝石的,是一个数组 (0, 1, 2,..., i)
, j
表示背包的容量,假设,我们这里一共有6和宝石,体积分别为 V = [2, 2, 6, 5, 4, 3]
,对应的价值分别是 W = [6, 3, 5, 4, 6, 2]
。
当背包容量 C = 1
时,则 F(0, 1) = 0; F(1, 1) = 0; ... ; F(5, 1) = 0
;
当背包容量 C = 2
时,则 F(0, 2) = 6; F(1, 2) = 6; ...; F(5, 2) = 6
;
当背包容量 C = 3
时,则 F(0, 3) = 6; F(1, 3) = 6; ...; F(5, 3) = 6
;
由此,我们可以得出结论,背包能装的宝石的最大价值和宝石数量及背包容量有关。
我们目的是求怎么样把n个宝石,最大价值的装到背包里。
我们做个假设: 先把下标从1开始计算。n个宝石的下标分别是1,2,3,...,n
- 第n个宝石,不是我们想要的宝石,那么
1,2,3,...,n-1
,就能求出我们所需的最大价值,用上面的函数表达式表示为:F(n-1, C)
; - 假设第
n
个宝石是我们想要的宝石,那么背包要把第n个宝石的空间减出来,剩余空间来装其他宝石,那么能装的最大价值的宝石函数表达式为:F(n-1, C-V[n])
; 则空间为C的背包能装的最大价值是F(n-1, C-V[n])+W[n]
这里只有这两种情况,所以,我们把这两种情况综合一下,最大值就是我们要求解的函数的最终值。 F(n, C) = MAX(F(n-1, C), F(n-1, C-V[n])+W[n])
那么,就是说 n
个宝石的最大价值和 n-1
个宝石的最大价值有关。
按照我们上面所说的步骤来求解:
F(n, C) F(n, C) = MAX(F(n-1, C), F(n-1, C-V[n])+W[n]) F(0, 0) = 0
代码实现如下:
struct Diamond { var id: String var volume: Int var value: Int var isSelected = false init(_ volume: Int, value: Int, id: String) { self.volume = volume self.value = value self.id = id } } class Knapsack { var number: Int // 物品数量 var C: Int // 背包最大体积或最大重量 var diamonds = Array<Diamond>() var V = Array<Array<Int>>() init(number: Int, C: Int) { self.C = C self.number = number // 初始化一个二维数组 self.V = initializeArray() // 初始化宝石对象 setDiamonds() // 打印现有的宝石 printDiamonds() } // 初始宝石数组 func setDiamonds() { for i in 0...number { if i == 0 { diamonds.append(Diamond(0, value: 0, id: "0")) } else { diamonds.append(Diamond(i + 1, value: i + 2, id: String(i))) } } } // 打印所有宝石 func printDiamonds() { for diamond in diamonds { print("id:\(diamond.id), value:\(diamond.value), volume:\(diamond.volume)") } } // 打印选中/未选中宝石 func printDiamonds(_ selected: Bool) { if selected { print("被选中的宝石:") } else { print("未被选中的宝石:") } for diamond in diamonds { if diamond.isSelected == selected && diamond.volume != 0 { print("id:\(diamond.id), value:\(diamond.value), volume:\(diamond.volume)") } } } // 初始化dp数组 func initializeArray() -> [[Int]] { var myArr = Array<Array<Int>>() for _ in 0...number { myArr.append(Array(repeating: 0, count: C+1)) } return myArr } func findOptimalSolution() -> Int { // i = 0, j = 0为边界条件,初始化的时候,初始化为0 // 填充二维数组 for i in 1...number { for j in 1...C { if j < diamonds[i].volume { // 当剩余的空间不够装这个宝石的时候,当前数组元素值与上个元素值相同 V[i][j] = V[i-1][j] } else { // 当剩余空间够装的下该宝石的时候,则动态规划该宝石是否要选中该宝石 V[i][j] = max(V[i-1][j], V[i-1][j-diamonds[i].volume] + diamonds[i].value) } } } // 二维数组最后一个元素就是最大价值 return V[number][C] } // 查找哪些宝石被选中 func findSelectedDiamonds(i: Int, j: Int) { if i > 0 { if V[i][j] == V[i-1][j] { diamonds[i].isSelected = false findSelectedDiamonds(i: i-1, j: j) } else { if j - diamonds[i].volume >= 0 && V[i][j] == V[i-1][j-diamonds[i].volume] + diamonds[i].value { diamonds[i].isSelected = true findSelectedDiamonds(i: i - 1, j: j - diamonds[i].volume) } } } } } 复制代码
用表格表示如下:
背包体积:1 | 背包体积:2 | 背包体积:3 | 背包体积:4 | 背包体积:5 | 背包体积:6 | 背包体积:7 | |
---|---|---|---|---|---|---|---|
宝石1 (volume = 2, worth = 6) |
0 | 6 | 6 | 6 | 6 | 6 | 6 |
宝石2 (volume = 2, worth = 3) |
0 | 6 | 6 | 9 | 9 | 9 | 9 |
宝石3 (volume = 6, worth = 5) |
0 | 6 | 6 | 9 | 9 | 9 | 9 |
宝石4 (volume = 5, worth = 4) |
0 | 6 | 6 | 9 | 9 | 9 | 10 |
宝石5 (volume = 4, worth = 6) |
0 | 6 | 6 | 9 | 9 | 12 | 12 |
最长上升子序列( longest increasing subsequence )
一个序列有 N
个数: A[1],A[2],…,A[N]
,求出最长非降子序列的长度。
分析这个问题: 我们定义一个数组 dp
, dp[i]
表示 0...i
之间序列的最大上升子序列,其中 i<N
。 拿个简单的输入举个例子:假设输入是: [10, 9, 2, 5, 3, 7, 101]
dp[0] = 1, ([10]) dp[1] = 1, ([10, 9]) dp[2] = 2, ([10, 9, 2]) dp[3] = 2, ([10, 9, 2, 5]) dp[4] = 2, ([10, 9, 2, 5, 3]) dp[5] = 3, ([10, 9, 2, 5, 3, 7]) dp[6] = 6, ([10, 9, 2, 5, 3, 7, 101]) 复制代码
想要求 dp(i)
,就把i前面的各个子序列中,最后一个数不大于 A[i]
的序列长度加1,然后取出最大的长度即为 dp(i)
。
按照上面的步骤求解:
dp[i] dp[i] = max(dp[j])+1, ∀0≤j<i dp[0] = 1
代码如下:
func lengthOfLIS(_ nums: [Int]) -> Int { if nums.count == 0 { return 0 } var dp = Array(repeating: 0, count: nums.count) dp[0] = 1 var maxAns = 1 for i in 1..<dp.count { var maxVal = 0 for j in 0..<i { if nums[i] > nums[j] { maxVal = max(maxVal, dp[j]) } } dp[i] = maxVal + 1 maxAns = max(maxAns, dp[i]) } return maxAns } 复制代码
二维动态规划问题
平面上有 N*M
个格子,每个格子中放着一定数量的苹果。你从左上角的格子开始,每一步只能向下走或是向右走,每次走到一个格子上就把格子里的苹果收集起来, 这样下去,你最多能收集到多少个苹果。
i
表示行, j
表示列 按照上面的步骤求解:
- 将大问题分解为子问题:
dp[i][j]
则和dp[i-1][j]
和dp[i][j-1]
有关, - 确定状态表示:
dp[i][j]
- 确定状态转移:
dp[i][j] = A[i][j] + max(dp[i-1][j], if i > 0; dp[i][j-1], if j > 0)
- 考虑初始状态和边界情况:
dp[0][0] = A[0][0]
伪代码实现:
int[][] dp for i = 0; i < N - 1; i++ for j = 0; j < M - 1; j++ if i == 0 dp[i][j] = dp[i][j-1] + A[i][j] if j == 0 dp[i][j] = dp[i-1][j] + A[i][j] else dp[i][j] = max(dp[i-1][j], dp[i][j-1]) return dp[N-1][M-1] 复制代码
参考链接:
以上所述就是小编给大家介绍的《动态规划简单介绍及Swift代码实现》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- DB 分库分表(5):一种支持自由规划无须数据迁移和修改路由代码的 Sharding 扩容方案
- Java学习路线规划
- 算法-动态规划
- 聊聊动态规划(2) -- 特征
- 聊聊动态规划(1) -- 概念
- Golang动态规划
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
垃圾回收的算法与实现
中村成洋、相川光 / 丁灵 / 人民邮电出版社 / 2016-7-1 / 99.00元
★ Ruby之父Matz作推荐语:上古传承的魔法,彻底揭开垃圾回收的秘密! ★ 日本天才程序员兼Lisp黑客竹内郁雄审校 本书前半介绍基本GC算法,包括标记-清除GC、引用计数、复制算法的GC、串行GC的算法、并发GC的算法等。后半介绍V8、Rubinius、Dalvik、CPython等几种具体GC的实现。本书适合各领域程序员阅读。一起来看看 《垃圾回收的算法与实现》 这本书的介绍吧!