动态规划_实战1
参考剑指offer
一、前言——递归与循环
即使同一个算法用循环和递归两种思路实现的时间效率可能会大不一样。
1.1、递归
1.1.1、递归的特点：
-
优点：
递归的本质是把一个大的复杂问题分解成两个或者多个小的简单的问题。
用递归实现会使代码显得很整洁 -
缺点：
如果小问题中有相互重叠的部分，时间效率可能会非常差。
1.2、数组 + 循环 —— 取其精华，去其糟粕
- 取其精华
对于这种类型的题目，我们可以用递归的思路分析问题， - 去其糟粕
但写代码的时候，不用递归实现， 可以用数组（一维或者多维数组）保存中间结果，并基于循环实现。
1.3 引入动态规划
绝大部分动态规划算法的分析和代码实现都是分这两个步骤完成的。
步骤1：用递归的思路分析问题
步骤2：用数组保存中间结果，并基于循环实现。
所以，接下来在实战的时候，会按照如下的思路，分析问题，并写出代码
问题建模：
- 1、分析问题，定义需要求的变量。
- 2、分析问题的三要素：边界条件，最优子结构，状态转移方程。
算法实现
- 3、用递归方法实现，验证模型的合理性
- 4、用数组保存中间结果，用循环，实现DP。
需要注意的地方：
一般，问题中有k个参数，可能DP的数组就是k-1维的。
比如，挖金矿问题中，有金矿数量和矿工人数两个参数，那么需要维护一个一维数组。
在合唱团问题中，有n，k，d三个参数，就需要维护二维数组。
二、实战
根据上面所说思路，分别用先建模，后递归，最后DP的算法解决问题。
2.1、爬楼梯问题
参考什么是动态规划
2.1.1问题建模
- 1、 设有F(N)种方法
- 2、根据三要素，可以进行建模（这里不多提了，可以参考进一步理解动态规划
） - 3、用递归实现
def climb(n):
if n == 1:
return 1
elif n == 2:
return 2
else:
return climb(n-1) + climb(n-2)
由前面递归可知，若是用DP自底向上的实现，那么每次需要记录当前n的前两个结果即可。
因此1、用一个数组把最优子结构的中间结果保存起来 2、在循环中不断地更新该数组。
- 4、DP
def climb_dp(n):
if n == 1:
return 1
elif n == 2:
return 2
#用一个数组把最优子结构的中间结果保存起来，在循环中不断地更新该数组
pre_list = [1,2]
for i in range(3,n+1):
f_i = pre_list[0] + pre_list[1]
pre_list[0] = pre_list[1]
pre_list[1] = f_i
return f_i
2.2、找零问题
2.2.1、问题建模
1、定义目标变量
设最少找零硬币数为F(N)
2、dp三要素
最优子结构：根据零钱与硬币面额的大小，最多有四个最优子结构
动态转移方程：F(N)等于最优子结构中的最小值，再加1
边界条件：N等于硬币面额
3、用递归写代码
#这个递归，运行起来真的会占用很长时间！
def makechange(n,coinValueList):
if n in coinValueList:
return 1
min_res = []
for i in coinValueList:
if n - i > 0:
min_res.append(makechange(n-i,coinValueList)+1)
print(min_res)
return min(min_res)
print(makechange(63,[1,5,10,25]))
4、从n=1开始一直到N，用一个数组保存最优子结构的值，一直循环到N
因为最优子结构有m个，所以中间会需要m此循环，用来计算每个最优子结构，用以在循环结束后选择最好得作为当前值的值。
def makechange_dp(n,coinValueList):
if n == 1:
return 1
#将中间会用到的每个零钱数的最少硬币数，用字典存起来
result = {}
result[1] = 1
for i in range(2,n+1):
min_coins = []
#利用状态转移方程计算每一个最优子结构需要的最少的硬币数，并选出最小值
for j in coinValueList:
if i > j:
min_coins.append(result[i-j] + 1)
result[i] = min(min_coins)
return result[n]
print(makechange_dp(63,[1,5,10,25]))
2.3、国王与金矿问题
建模参考进一步理解动态规划
递归实现：
- 时间复杂度
因为每个状态有两个最优子结构，所以递归的执行流程类似于一颗高度为N的二叉树。
方法的时间复杂度是O(2^N)。
def getMostGold(m,n,gold_list,miner_list):
#边界条件
if m == 1 and n < miner_list[0]:
return 0
elif m == 1 and n >= miner_list[0]:
return gold_list[0]
#这个情况也是需要考虑的，如果最后一个矿需要的工人数大于总工人数n，
# 那么绝对不会动最后一个矿
elif m > 1 and n < miner_list[m-1]:
return getMostGold(m-1,n,gold_list,miner_list)
#状态转移方程，在人数充足，并且n大于最后一个矿工人数时，可以用状态转移方程
else:
return max(getMostGold(m-1,n,gold_list,miner_list),
getMostGold(m-1,n-miner_list[m-1],gold_list,miner_list) + gold_list[m-1])
print(getMostGold(5,10,[500,200,300,350,400],[5,3,4,3,5]))
动态规划
怎么确定需要保存的数组？
递归的进一步算法是备忘录算法，可以通过备忘录算法，来找到比DP保存的中间数组稍微大的数组。
自底向上的实现，根据网页中画的表格可以帮助理解。
也可以从另一方面思考。
1、循环数：
有两个参数维度，就用两个循环实现。最外层循环为矿数m，内层循环为工人数n。
2、需要保存的数组：
由状态转移方程可知，当有m个矿时，F(m,n)是由m-1时的两个状态决定的
因此只需要保存矿数为m-1的n个状态即可，因此需要构造一个长度为n的list用来保存中间结果
怎样根据第m-1个list中的每个格子，推断出第m个list中的每个格子的数值。。。不能确定状态转移方程的每个具体参数时，可以举例子来直观理解。
- 根据图表，可以举例看到，前面的每一行都是最优值
- 求2个金矿8个人时，可以根据，状态转移方程，若是挖第2个矿，此时用掉3个人，得到200黄金
- 因此此时黄金数是，200+1个矿时（8-3）个矿工的最优值。
- 若是不挖第2个矿，那此时最优值就是1个矿时8个矿工的最优值。
代码实现:
def getMostGold_dp(m,n,gold_list,miner_list):
#根据边界条件，在金矿数为1时，得到初始list
mid_res = [ ]
#注意，中间结果保存的是矿工人数为1到10人的情况，如果只是range(n)，那么就是0-9的情况
for i in range(1,n+1):
if i < miner_list[0]:
mid_res.append(0)
else:
mid_res.append(gold_list[0])
print(mid_res)
for i in range(1,m):
#根据状态转移方程，得到矿数一定为m-1时，人数不同对应的各种状态
m_result = []
for j in range(n):
#若是人数小于最后一个矿所需 矿工数，那就直接按上一个来
if j - miner_list[i] < 0:
m_result.append(mid_res[j])
else:
m_result.append(max(gold_list[i] + mid_res[j-miner_list[i]],mid_res[j]))
mid_res = m_result
print(mid_res)
return mid_res
getMostGold_dp(5,10,[500,200,300,350,400],[5,3,4,3,5])
