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背包问题
0-1 背包问题：有件物品和有一个最多能装重量为的背包。第件物品的重量为，价值为，每件物品有且只有件。请问在总重量不超过背包载重上限的情况下，能装入背包的最大价值是多少？
type
status
date
slug
summary
tags
category
icon
password
Property
目录
区间 DP
区间动态规划：线性 DP 的一种，简称为「区间 DP」。以「区间长度」划分阶段，以两个坐标（区间的左、右端点）作为状态的维度。一个状态通常由被它包含且比它更小的区间状态转移而来。
区间 DP 的主要思想就是：先在小区间内得到最优解，再利用小区间的最优解合并，从而得到大区间的最优解，最终得到整个区间的最优解。
根据小区间向大区间转移情况的不同，常见的区间 DP 问题可以分为两种：
- 单个区间从中间向两侧更大区间转移的区间 DP 问题。比如从区间转移到更大区间
- 多个（大于等于 2 个）小区间转移到大区间的区间 DP 问题。比如从区间和区间转移到区间
第1种区间 DP 问题基本思路
从中间向两侧转移的区间 DP 问题的状态转移方程一般为：
type
status
date
slug
summary
tags
category
icon
password
Property
数据库对比
常见的内存型数据库，除
Redis之外，还有 Oracle Berkeley DB（甲骨文旗下的一款产品）、SQlite（轻量级内存数据库）、Memcache（键值型分布式缓存数据库）、Altibase（基于内存的高性能数据库）。与其他内存型数据库相比，
Redis具有以下特点：Redis不仅可以将数据完全保存在内存中，还可以通过磁盘实现数据的持久存储
Redis支持丰富的数据类型，包括string、list、set、zset、hash等多种数据类型，也被称为“数据结构服务器”
Redis支持主从同步，即master-slave主从复制模式。数据可以从主服务器向任意数量的从服务器上同步，有效地保证数据的安全性
Redis支持多种编程语言，包括C、C++、Python、Java、PHP、Ruby、Lua等
与
SQL型数据库截然不同，Redis没有提供新建数据库的操作，因为它自带了16 （0—15）个数据库（默认使用0库）。在同一个库中，key是唯一存在的、不允许重复的，它就像一把“密钥”，只能打开一把“锁”。键值存储的本质就是使用key来标识value，当想要检索value时，必须使用与value相对应的key进行查找。Redis数据库没有“表”的概念，它通过不同的数据类型来实现存储数据的需求，不同的数据类型能够适应不同的应用场景，从而满足开发者的需求。
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 类型：聚合计算（并集、交集、差集）场景，比如点赞、共同关注、抽奖活动等
- Zset 类型：排序场景，比如排行榜、电话和姓名排序等
