动态规划第一讲
把难题放一边，先来理解动态规划中的一些重要概念
- 状态转移方程
- 重叠子问题
- 备忘录剪枝
- 状态压缩
1.1递推与动态规划
要理解动态规划的基本解题思路，先来做一道高中数学题
通俗来讲 动态规划 算法并不直接给出最终结果的求解表达式，而是通过找到问题规模之间的 动态转移方程，借此不断缩小问题规模，逐渐迫近 base case。所谓动态转移方程就是不同规模问题之间的关系，类似递推式。
1.1.1自顶向下解法
def func(n):
if n == 0:
return 2
return func(n - 1) + 3
所谓自定向下解法就是使用函数递归，递归的计算过程正如上图紫线箭头方向
1.1.2 自底向上解法
def func2(n):
# 确定dp[i] 的含义
# d[i] == func(i)
# dp数组规模,规模与dp[i]的定义密切相关
# 根据dp[i] 定义，func2(n) 对应dp[n]
# 要使得dp[n] 合法，数组长度要为 n+1
dp = [0] * (n + 1)
# base_case
dp[0] = 2
# dp数组的遍历顺序
# func(i) = func(i-1) + 3
# dp[i] = dp[i-1] + 3
for i in range(1, n + 1):
dp[i] = dp[i - 1] + 3
return dp[n]
所谓自底向上解法就是利用一个数组存储计算过程产生的值，计算过程正如上图绿色箭头方向
1.2重叠子问题
直观了解了 状态转移方程后，以 斐波那契额数列问题为例看 重叠子问题。
$ F(0)=0, \quad F(1)=1,\quad F(n)=F(n-1)+F(n-2) \quad\left(n \geq 2, \quad n \in N^{*}\right) $
1.2.1自顶向下解法
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
return fib(n - 1) + fib(n - 2)
1.2.2 观察重叠子问题
def fib(n):
# 查看函数调用次数，看见"重叠子问题"
print("函数调用func(", n, ")")
if n == 0:
return 0
elif n == 1:
return 1
return fib(n - 1) + fib(n - 2)
python3 test.py | grep "( 0 )" -c
4181
python3 test.py | grep "( 10 )" -c
89
python3 test.py | grep "( 15 )" -c
8
python3 test.py | grep "( 20 )" -c
1
不难发现， fib(0) 被执行了4181次， fib(10) 被执行了89次， fib(15) 被执行了8次。。。
重叠子问题导致了大量的重复计算。并且重复的计算量随着问题规模增大极速上升。
因此，使用 备忘录 来减少重复计算非常有必要！
1.2.3 自顶向下 + 备忘录
# 使用一个字典存储计算过得fib(n)
# base_case 也可直接放入备忘录
# 字典以 n为键，fib(n) 为值
memo = {0: 0, 1: 1}
def fib1(n):
# 如果备忘录中有记载，直接返回
print("函数调用func(", n, ")")
if n in memo.keys():
return memo[n]
val = fib1(n - 1) + fib1(n - 2)
memo[n] = val
return val
python3 try.py
函数调用func( 20 )
函数调用func( 19 )
函数调用func( 18 )
函数调用func( 17 )
函数调用func( 16 )
函数调用func( 15 )
函数调用func( 14 )
函数调用func( 13 )
函数调用func( 12 )
函数调用func( 11 )
函数调用func( 10 )
函数调用func( 9 )
函数调用func( 8 )
函数调用func( 7 )
函数调用func( 6 )
函数调用func( 5 )
函数调用func( 4 )
函数调用func( 3 )
函数调用func( 2 )
备忘录相当于为整个递归遍历树进行了一个 剪枝操作。
1.2.4 自底向上
def fib2(n):
# 确定dp[i]的含义
# dp[i] = fib(i)
# dp数组规模
dp = [0] * (n + 1)
# base_case
dp[0] = 0
dp[1] = 1
# dp 数组遍历方向
# fib(i) = fib(i-1) + fib(i-2)
# dp[i] = dp[i-1] + dp[i-2]
# dp[大] 依赖 dp[小] 所以先算dp[小]
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
使用dp数组自顶向下来解不存在 重叠子问题。
空间开销为 O(n)，不难看出，每次计算新值只依赖前面两个值。因此我们可以使用两个变量来记录，而不使用dp数组。
1.2.5 自底向上 + 状态压缩
def fib3(n):
if n == 0:
return 0
if n == 1 or n == 2:
return re1
# prev初始为dp[1]
prev = 1
# curr初始为dp[2]
curr = 1
# 注意迭代次数
# 注意i = 3时，迭代了1轮，迭代结束 curr == dp[3]
# 注意i = 4时，迭代了2轮，迭代结束 curr == dp[4]
# 所以 i = n 时，迭代结束时 curr == dp[n]
# range 前闭后开 so ...
for i in range(3, n + 1):
sum = prev + curr
prev = curr
curr = sum
return curr
当出现重叠子问题时， 自定向下的解法一需要 备忘录来 剪枝， 自底向上的解法二需要 状态压缩减少空间开销。
一般来说，自顶向下的方法如果不用备忘录剪枝，一般会超时。自底向上的方法不进行状态压缩一般也没事。
1.3总结
自顶向下 自底向上 编程方式 递归 数组 额外辅助 备忘录，用于剪枝 状态压缩 若不使用辅助 一般超时，重复子问题往往指数级增加计算量 一般没事，一些情况也不容易状态压缩。不压缩往往是O(n)、 O(n^2) 空间复杂度
Original: https://www.cnblogs.com/orangeQWJ/p/16793356.html
Author: orangeQWJ
Title: 动态规划（一）极速入门
相关阅读
Title: Numpy库 array相关操作
2、list转array 获取array形状
array属于numpy库
import numpy as np
L = [[1,2],[3,4],[5,6],[7,8]]
L = np.array(L)
print(L.shape)
array的shape属性
print(L.shape)
(4, 3)
>>> print(y.shape[0])
4
>>> print(y.shape[1])
3
3、array 水平 拼接
有两个数组a和b
>>> a
array(［0, 1, 2],
[3, 4, 5],
[6, 7, 8］)
>>> b = a*2
>>> b
array(［ 0, 2, 4],
[ 6, 8, 10],
[12, 14, 16］)
第一个是可读性和灵活性的，但占用大量内存。第二种不存在内存占用量大的问题。
[En]
The first one is readable and flexible, but takes up a lot of memory. The second does not have the problem of large memory footprint.
>>> np.hstack((a,b))
array(［ 0, 1, 2, 0, 2, 4],
[ 3, 4, 5, 6, 8, 10],
[ 6, 7, 8, 12, 14, 16］)
>>> np.concatenate((a,b),axis=1)
array(［ 0, 1, 2, 0, 2, 4],
[ 3, 4, 5, 6, 8, 10],
[ 6, 7, 8, 12, 14, 16］)
请注意，只有具有相同维度的那些才能合并。
[En]
Note that only those with the same dimension can be merged.
(642, 202, 2)
(642, 202)
ValueError: all the input arrays must have same number of dimensions, but the array at index 0 has 3 dimension(s) and the array at index 1 has 2 dimension(s)
4、Numpy的array分割
aaa = np.arange(10).reshape((5, 2))
print(aaa)
a, b = np.split(aaa, 2, axis=1)
print(a)
print(b)
[[0 1]
[2 3]
[4 5]
[6 7]
[8 9]]
[[0]
[2]
[4]
[6]
[8]]
[[1]
[3]
[5]
[7]
[9]]
5、将array保存到txt文件
np.savetxt()
np.savetxt('E:/2020_pre/new/data', data, delimiter=" ")
'''
文件路径
要保存的数组名
delimiter=" "表示分隔符，这里以空格的形式隔开
'''
np.loadtxt(fname)
将数据读出为array类型,fname表示需要加载的文件名及其路径
6、numpy.save()将数组存储成npy类型文件
np.save('arraytest.npy',ar)
ar_load = np.load('arraytest.npy')
print(ar_load)
Original: https://blog.csdn.net/weixin_42921195/article/details/123504978
Author: Ru-0908
Title: Numpy库 array相关操作
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/363489/
转载文章受原作者版权保护。转载请注明原作者出处！
