type
status
date
slug
summary
tags
category
icon
password
Property
目录
动态规划(Dynamic Programming):简称 DP,是一种求解多阶段决策过程最优化问题的方法。在动态规划中,通过把原问题分解为相对简单的子问题,先求解子问题,再由子问题的解而得到原问题的解。
动态规划的核心思想:
- 把「原问题」分解为「若干个重叠的子问题」,每个子问题的求解过程都构成一个 「阶段」。在完成一个阶段的计算之后,动态规划方法才会执行下一个阶段的计算。
- 在求解子问题的过程中,按照「自顶向下的记忆化搜索方法」或者「自底向上的递推方法」求解出「子问题的解」,把结果存储在表格中,当需要再次求解此子问题时,直接从表格中查询该子问题的解,从而避免了大量的重复计算。
这看起来很像是分治算法,但动态规划与分治算法的不同点在于:
type
status
date
slug
summary
tags
category
icon
password
Property
记忆化搜索(Memoization Search):是一种通过存储已经遍历过的状态信息,从而避免对同一状态重复遍历的搜索算法。
记忆化搜索是动态规划的一种实现方式。在记忆化搜索中,当算法需要计算某个子问题的结果时,它首先检查是否已经计算过该问题。如果已经计算过,则直接返回已经存储的结果;否则,计算该问题,并将结果存储下来以备将来使用。
为了避免重复计算,在递归的同时,我们可以使用一个缓存(数组或哈希表)来保存已经求解过的的结果。当递归调用用到时,先查看一下之前是否已经计算过结果,如果已经计算过,则直接从缓存中取值返回,而不用再递推下去,这样就避免了重复计算问题。
记忆化搜索与递推区别
「记忆化搜索」与「递推」都是动态规划的实现方式,但是两者之间有一些区别。
记忆化搜索:「自顶向下」的解决问题,采用自然的递归方式编写过程,在过程中会保存每个子问题的解(通常保存在一个数组或哈希表中)来避免重复计算。
type
status
date
slug
summary
tags
category
icon
password
Property
目录
线性动态规划:具有「线性」阶段划分的动态规划方法统称为线性动态规划(简称为「线性 DP」)
如果状态包含多个维度,但是每个维度上都是线性划分的阶段,也属于线性DP。比如背包问题、区间DP、数位DP等都属于线性DP。线性DP问题的划分方法有多种方式。
- 如果按照「状态的维度数」进行分类,可以将线性DP问题分为:一维线性DP问题、二维线性DP问题,以及多维线性DP问题。
- 如果按照「问题的输入格式」进行分类,可以将线性DP问题分为:单串线性DP问题、双串线性DP问题、矩阵线性DP问题,以及无串线性DP问题。
type
status
date
slug
summary
tags
category
icon
password
Property
目录
背包问题是线性 DP 问题中一类经典而又特殊的模型。背包问题可以描述为:给定一组物品,每种物品都有自己的重量、价格以及数量。再给定一个最多能装重量为的背包。现在选择将一些物品放入背包中,请问在总重量不超过背包载重上限的情况下,能装入背包的最大价值总和是多少?
根据物品限制条件的不同,背包问题可分为:0-1 背包问题、完全背包问题、多重背包问题、分组背包问题,以及混合背包问题等。
背包问题的暴力解题:假设有件物品,枚举出这件物品所有可能的组合。然后再判断这些组合中的物品是否能放入背包,以及是否能得到最大价值。这种做法的时间复杂度是,复杂度是指数级别的,可以利用动态规划算法减少一下时间复杂度。
0-1背包问题
type
status
date
slug
summary
tags
category
icon
password
Property
目录
区间 DP
区间动态规划:线性 DP 的一种,简称为「区间 DP」。以「区间长度」划分阶段,以两个坐标(区间的左、右端点)作为状态的维度。一个状态通常由被它包含且比它更小的区间状态转移而来。
区间 DP 的主要思想就是:先在小区间内得到最优解,再利用小区间的最优解合并,从而得到大区间的最优解,最终得到整个区间的最优解。
根据小区间向大区间转移情况的不同,常见的区间 DP 问题可以分为两种:
- 单个区间从中间向两侧更大区间转移的区间 DP 问题。比如从区间转移到更大区间
- 多个(大于等于 2 个)小区间转移到大区间的区间 DP 问题。比如从区间和区间转移到区间
第1种区间 DP 问题基本思路
type
status
date
slug
summary
tags
category
icon
password
Property
Redis
全称Remote Dictionary Server
(远程字典服务),是一个基于内存实现的键值型非关系(NoSQL)数据库,由意大利人Salvatore Sanfilippo
用C
语言编写。Redis
遵守BSD协议,实现了免费开源。自诞生以来,以其超高的性能、完美的文档和简洁易懂的源码广受好评,国内外很多大型互联网公司都在使用Redis
,比如腾讯、阿里、Twitter、Github
等等。数据库对比
常见的内存型数据库,除
Redis
之外,还有 Oracle Berkeley DB
(甲骨文旗下的一款产品)、SQlite
(轻量级内存数据库)、Memcache
(键值型分布式缓存数据库)、Altibase
(基于内存的高性能数据库)。type
status
date
slug
summary
tags
category
icon
password
Property
Redis
命令用于在Redis
服务器上执行一些操作,而命令运行的方式是通过客户端命令行来执行的,这种方式也被称为“命令行模式”。因此想要 Redis
服务器上运行命令,首先需要开启一个Redis
客户端:注意:在开启客户端之前,要确定
Redis
服务器已经开启本地服务器运行命令
本地服务器指的是,
Redis
服务器和客户端安装在同一台计算机上。在计算机上打开一个Redis
客户端输入以下命令,验证客户端与Redis
服务器是否成功连接。通过执行命令
ping
,检查服务器是否正在运行,结果返回PONG
,说明已经成功连接了本地Redis
服务器远程服务器上运行命令
type
status
date
slug
summary
tags
category
icon
password
Property
目录
Redis 提供了丰富的数据类型,常见的有五种数据类型:String(字符串),Hash(哈希),List(列表),Set(集合)、Zset(有序集合)。
随着Redis版本的更新,后面又支持了四种数据类型: BitMap(2.2 版新增)、HyperLogLog(2.8 版新增)、GEO(3.2 版新增)、Stream(5.0 版新增),
Redis
数据类型的应用场景:- String 类型的应用场景:缓存对象、常规计数、分布式锁、共享 session 信息等
- List 类型的应用场景:消息队列(但是有两个问题:1. 生产者需要自行实现全局唯一 ID;2. 不能以消费组形式消费数据)等
- Hash 类型:缓存对象、购物车等
- Set 类型:聚合计算(并集、交集、差集)场景,比如点赞、共同关注、抽奖活动等