# 动态规划第一讲

• 状态转移方程
• 重叠子问题
• 备忘录剪枝
• 状态压缩

## 1.1递推与动态规划

### 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


### 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



### 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]


### 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总结

Original: https://www.cnblogs.com/orangeQWJ/p/16793356.html
Author: orangeQWJ
Title: 动态规划（一）极速入门

## 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
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)


## 6、numpy.save()将数组存储成npy类型文件

np.save('arraytest.npy',ar)






Original: https://blog.csdn.net/weixin_42921195/article/details/123504978
Author: Ru-0908
Title: Numpy库 array相关操作

(0)

### 大家都在看

• #### 【Vue】webpack的基本使用

✍️ 作者简介: 前端新手学习中。 💂 作者主页: 作者主页查看更多前端教学 🎓 专栏分享：css重难点教学 Node.js教学 从头开始学习 ajax学习 文章目录 webpac…

Python 2023年1月23日
017
• #### MNN简介

一、轻量级高性能推理引擎 1.简介 MNN 是一个高效、轻量的深度学习框架。它支持深度模型推理与训练，尤其在端侧的推理与训练性能在业界处于领先地位。目前，MNN 已经在阿里巴巴的手…

Python 2023年1月19日
019
• #### 一文读懂野指针

一、引子 我们都知道对指针（ Pointer）的操作，实际上是对计算机内存地址的操作，通过访问内存地址实现间接访问该地址中保存的数据。其实就是CPU的寻址方式中的间接寻址。简单概括…

Python 2023年1月28日
026
• #### 30个精品Python练手项目

前言： 随着 Python 语言的流行，越来越多的人加入到了 Python 的大家庭中。到底为什么这么多人学 Python ？我要喊出那句话了：”人生苦短，我用 Pyt…

Python 2022年12月23日
041
• #### seed()函数

不管是再深度学习还是在其他工作中，相信大家经常会碰到seed()函数，一定有许多同学搞不清楚其作用，传入的参数数值（即seed(num),num对应的数字）应该是多少。下面一一给大…

Python 2023年1月12日
066
• #### 一文理解Linux的基本指令（下）（三分钟学会Linux基本指令）

前言：衔接上一篇文章，继续总结一下Linux操作系统的指令，不会有人认为Linux系统指令只有上篇文章那么多了吧，嘿嘿小马告诉你可不止这么多，而我这篇文章总结完，也只是我们所用的比…

Python 2023年1月28日
033
• #### 【计算机视觉】图像分割与特征提取——基于Roberts、Prewitt、Sobel算子的图像分割实验

个人简介： 📦个人主页：赵四司机🏆学习方向：JAVA后端开发⏰往期文章：SpringBoot项目整合微信支付🔔博主推荐网站：牛客网 刷题|面试|找工作神器📣种一棵树最好的时间是十年…

Python 2023年1月19日
045
• #### Python爬虫何如抓包？这三个案例手把手教会你，非常详细…

很多朋友总是问我怎么找到数据源，怎么抢袋子。其实很简单，再做几次手术我就记住了。 [En] Many friends always ask me how to find the d…

2022年9月3日
098
• #### （萌新向很详细！）在Anaconda下安装Pytorch环境流程及问题总结

（萌新向很详细！）Anaconda下安装Pytorch环境流程及问题总结 目录 前言 一、Anaconda是什么？Pytorch是什么？ Anaconda是什么？ Pytorch是…

Python 2023年1月19日
027
• #### CVE-2021-32849 Gerapy远程命令执行漏洞复现

0x01 漏洞描述 Gerapy是基于Scrapy；Scrapyd；Scrapyd-Client；Scrapyd-API；Django和Vue.js的分布式爬虫管理框架。 本文利用…

Python 2022年12月26日
028
• #### centos7篇—centos7中安装mongodb

centos7中安装mongodb 方式一： * 1. 安装环境 2. 安装过程 启用授权验证 方式二： * RHEL/CentOS 用户 刷新缓存并安装 mongodb-org。…

Python 2023年1月19日
019
• #### numpy 对二维数组的常用操作

1、提取二维数组的某几列或某几行 2、获取某个范围的数据 3、所有元素求和 4、计算数组中非零元素的个数 5、使用布尔型掩码提取某些行或某些列 6、获取数组的行数或列数 7、获取最…

Python 2023年1月11日
050
• #### scrapy异步写入mysql_scrapy之异步写入数据库

1 setting.py文件,写入数据库连接属性# mysql连接属性 MYHOST = ‘127.0.0.1’ MYUSER = ‘root&…

Python 2023年1月26日
020
• #### 点云 数据 （偏向于研究大小）

组成 前三个是x,y,z 坐标 后三个是颜色，RGB property float x property float y property float z property uch…

Python 2023年1月10日
020
• #### 数据分析处理库-Pandas基础-上篇

; 数据分析处理库- Pandas基础-上篇 1 pandas简介 高性能,易使用的数据分析工具 可以做什么? 处理多种类型的数据 SQL.Excel,等类似含有异构列的数据 有序…

Python 2022年12月29日
023
• #### Scrapy 爬虫初体验

下载安装： conda install -c scrapinghub scrapy 初始化在空白文件夹下创建项目文件夹 [En] Initialize the creation o…

Python 2023年1月26日
019