一、Redis

1. 为什么在这个场景引入 Redis？

在店铺营业状态这个场景中：

• 数据特点：只有两种状态（营业 / 打烊）、读多写少（频繁查询状态）、对实时性要求高
• 如果用 MySQL：需要建表，增加系统复杂度、每次查询需要 IO，性能较低

因此选择使用 Redis（内存数据库） 来存储状态：

• 基于内存，读写性能高（微秒级）
• 适合存储简单 KV 结构
• 可以减少数据库压力

2. Redis 在项目中的使用流程

1. 引入依赖：spring-boot-starter-data-redis
2. 配置连接信息：host / port / password / database
3. 配置 RedisTemplate 类：设置 key/value 序列化器（避免乱码）
4. 业务操作：set / get

3. 为什么要配置序列化器？

RedisTemplate 默认使用 JDK 序列化：可读性差（乱码）、跨语言兼容性差

在项目中：

• key：StringRedisSerializer
• value：String / JSON 序列化

好处：可读性强、便于调试、通用性好

4. 怎么设计Key？

全局设置一个常量：

1

public static final String KEY = "SHOP_STATUS";

5. Bug 排查过程（重点）

你这段非常好，但需要“面试表达化”👇

问题：

1

RedisConnectionFailureException: Unable to connect to Redis

排查思路（一定要按层次说！）：

（1）排除 Spring Bean 问题

• redisTemplate 成功注入（打印 redisTemplate对象）

（2）排除 Redis 服务问题

• redis-cli 连接正常 (redis-cli)

（3）排除配置文件问题

• host / port / database 读取正常（@value）

（4）定位到连接工厂（关键）

• RedisConnectionFactory 创建失败 ❌

最终定位：Lettuce 客户端连接阶段失败

6. 问题本质原因

在 Windows 环境下，Redis 开启密码认证时，Lettuce 客户端在认证阶段存在兼容问题，导致连接失败。

7. 解决方案（要说“方案 + 扩展”）

当前方案：

• 去掉 Redis 密码 → 成功连接

更优方案（面试加分）：

• 使用 Docker + Linux 版本 Redis
• 或切换 Jedis

扩展问题

• Redis 和 MySQL 的区别？
• Redis 为什么快？
• Redis 持久化机制（RDB / AOF）
• Redis 线程模型（单线程 + IO 多路复用）

二、微信小程序登录 + JWT

1. 小程序登录流程

1. 小程序调用 wx.login → 获取 code
2. 客户端将 code 发送给后端
3. 后端调用微信接口（通过 HttpClient）
4. 微信返回：
   • openid（用户唯一标识）
5. 后端：
   • 根据 openid 查询 / 注册用户
   • 生成 JWT token
6. 返回 token 给前端
7. 前端后续请求携带 token

2. 为什么需要 openid？

• openid 是微信用户在当前小程序中的唯一标识
• 用于：用户登录、用户数据绑定

3. HttpClient 的作用

HttpClient 用于：

• 构造 HTTP 请求（GET/POST）
• 发送请求
• 接收响应

本质：服务端调用第三方 API（微信服务器）

4. JWT 的作用

用于实现 无状态登录（Stateless Authentication）

5. JWT 的组成

三部分：

1

Header.Payload.Signature

• Header：算法信息
• Payload：用户数据（userId、过期时间）
• Signature：签名防篡改

6. 在项目中 JWT 是怎么用的？

• 登录成功后：
  • 生成 JWT token
  • 将 userId、时效写入 payload
• 返回 token 给前端
• 前端请求时：
  • 放在请求头（Authorization / token）

7. 拦截器做了什么？（重点）

在 Spring 中通过 HandlerInterceptor：

1. 判断是否是需要拦截的请求
2. 获取请求头中的 token
3. 解析 JWT：
   • 成功 → 放行
   • 失败 → 拒绝请求

8. 为什么用 JWT，而不是 Session？（重点）

我的选择原因：

• 支持分布式
• 减少服务器压力
• 易扩展

9. 拓展问题

• JWT 会不会被篡改？
• JWT 如何续期？
• JWT 如何退出登录？
• Token 存在哪更安全？

三、总结

技术点：

• Redis（缓存设计 + 问题排查）
• JWT（认证体系）
• HttpClient（第三方接口调用）
• Spring 拦截器

学习资料与完整代码

已整理并上传至 GitHub 仓库

区间 DP 的本质是：在一个连续区间内枚举“最后一次决策点”，把区间拆分成若干更小区间，通过最优子结构组合得到整体最优解。它解决的是“前缀 DP 无法表达的、区间内相互依赖的问题”。

一、为什么需要区间 DP（与线性 DP 的根本区别）

线性 DP 在解决什么问题？

• 状态通常是：前 i 个元素
• 决策是：当前位置选 or 不选
• 子问题天然是前缀 / 后缀

例如：

• LIS
• LCS
• 背包
• 股票状态机

哪些问题线性 DP 无法直接建模？

当问题满足以下特征之一时，几乎必然是区间 DP：

• 决策发生在区间内部，而不是边界
• 子问题不是“前 i 个”，而是“任意子区间”
• 当前最优解依赖于区间被切成两段或多段

这时就必须显式引入「区间左右端点」。

二、区间 DP 的标准状态定义

区间 DP 的统一模板：

1

dp[i][j] 表示：区间 [i, j] 内的最优解

常见的隐含约束：

• i <= j
• 区间长度逐渐变大
• 转移依赖更小的区间

三、经典入门：516 最长回文子序列

状态定义

1

dp[i][j]：字符串 s 在区间 [i, j] 内的最长回文子序列长度

边界条件

• i > j：空区间 → 0
• i == j：单字符 → 1

状态转移

• 如果 s[i] == s[j]：

1

dp[i][j] = dp[i+1][j-1] + 2

• 如果 s[i] != s[j]：

1

dp[i][j] = max(dp[i+1][j], dp[i][j-1])

遍历顺序（区间 DP 的“坑点”）

dp[i][j] 依赖：

• dp[i+1][j]
• dp[i][j-1]
• dp[i+1][j-1] 对于 i 来说是后面的状态，对于 j 来说是前面的状态

因此：

• i 必须从大到小
• j 必须从小到大

1
2

for i = n-1 .. 0:
    for j = i .. n-1:

常见易错点

• 区分「子序列」与「子串」：一个可以不连续，一个必须连续

四、区间切分模型：1039 多边形三角剖分

抽象模型

这类问题的统一抽象是：

在区间 (i, j) 中，枚举一个“最后参与决策的点 k”

状态定义

1

dp[i][j]：由顶点 i 到 j 构成的多边形的最低三角剖分得分

状态转移（「枚举中点」为例）

1
2
3
4

dp[i][j] = min over k ∈ (i, j):
    dp[i][k] +
    values[i] * values[k] * values[j] +
    dp[k][j]

其中：

• (i, k) 和 (k, j) 是两个子多边形
• (i, k, j) 是当前枚举的三角形

这是区间 DP 最典型的结构，与回文问题完全不同，但模型统一。

本质理解

• 固定一条边 (i, j)
• 枚举“与这条边形成三角形的顶点 k”
• 将问题拆成左右两个区间

五、极值对抗模型：375 猜数字大小 II

为什么它也是区间 DP？

因为：

• 每次选择一个 k
• 会把区间 [l, r] 分成：
  • [l, k-1]
  • [k+1, r]

状态定义

1

dp[l][r]：在区间 [l, r] 内保证猜中所需的最少现金

状态转移（min + max 的组合）

1
2

dp[l][r] = min over k ∈ [l, r]:
    k + max(dp[l][k-1], dp[k+1][r])

为什么是 max？

• 因为要保证“最坏情况下也能赢”
• 属于 对抗型 / 博弈型区间 DP

六、区间 DP 的统一分类总结

七、区间 DP 的工程级思维模型

建模四步法

1. 区间 [i, j] 表示什么？
2. 决策发生在区间的哪里？
3. 子区间如何划分？
4. 边界区间是什么？

遍历顺序的通用规律

• 区间长度从小到大
• 或等价地：
  • i 从大到小
  • j 从小到大

谁正谁反，取决于你依赖的是 i+1 还是 j-1。

相关代码

本文涉及的所有代码与笔记，均已同步至我的 GitHub 算法仓库，作为 Java 后端校招过程中的学习记录。

状态机 DP 的本质是：在时间线推进的过程中，用有限个状态描述系统所处阶段，并在状态之间进行合法转移，求全局最优解。股票系列问题是状态机 DP 最经典、也最具迁移价值的模型。

一、什么是状态机 DP

不是“多维 DP”这么简单

状态机 DP 的核心特征

• 时间维度是线性的（天数 / 下标 i）
• 状态集合是有限且很小的（通常 2～5 个）
• 每一天的最优解，只依赖于：
  • 前一天（或前几天）
  • 合法状态之间的转移

典型形式：

1
2
3

dp[i][state] = max / min {
    dp[i-1][prev_state] + cost
}

为什么股票问题天然适合状态机 DP？

因为每天的行为是有限的：

• 买
• 卖
• 什么都不做

而这些行为，本质上只会改变“是否持有股票”这一状态。

二、股票问题的统一状态定义

不管题目怎么变，本质都围绕这两个基础状态：

1
2

state = 0 → 当前不持有股票
state = 1 → 当前持有股票

因此最基础的定义是：

1

dp[i][j] 表示：第 i 天结束后，处于状态 j 时的最大利润

三、基础模型：122 买卖股票的最佳时机 II（无限次交易）

状态定义

1
2

dp[i][0]：第 i 天结束后，不持股的最大利润
dp[i][1]：第 i 天结束后，持股的最大利润

状态转移（状态机视角）

不持股（state = 0）

• 昨天就不持股，今天什么都不做
• 昨天持股，今天卖出

1
2
3
4

dp[i][0] = max(
    dp[i-1][0],
    dp[i-1][1] + prices[i]
)

持股（state = 1）

• 昨天就持股，今天继续持有
• 昨天不持股，今天买入

1
2
3
4

dp[i][1] = max(
    dp[i-1][1],
    dp[i-1][0] - prices[i]
)

这是最纯粹的状态机 DP 模型，后续所有变形都在此基础上增加约束。

四、加入约束一：冷冻期（309）

买入操作不再只依赖前一天。

卖出后，下一天不能立刻买入，因此：

• 买入只能从 前两天的不持股状态 转移

状态转移变化

1
2
3
4
5
6
7
8
9

dp[i][0] = max(
    dp[i-1][0],
    dp[i-1][1] + prices[i]
)

dp[i][1] = max(
    dp[i-1][1],
    dp[i-2][0] - prices[i]
)

这类题的本质不是“新增状态”，而是：转移来源发生了变化

五、加入约束二：交易次数限制（188 / 123）

为什么要引入「交易次数」维度？

因为一次完整交易 = 买入 + 卖出
限制交易次数，意味着 dp 数组中必须记录“还剩几次卖出的机会”。

状态定义（标准三维状态机）

1
2
3
4
5

dp[i][k][j]
表示：第 i 天结束后，
      还剩 k 次交易机会，
      当前状态为 j（0 不持股 / 1 持股）
      的最大利润

核心转移逻辑（只在卖出时消耗交易次数）

1
2
3
4
5
6
7
8
9

dp[i][k][0] = max(
    dp[i-1][k][0],
    dp[i-1][k-1][1] + prices[i]
)

dp[i][k][1] = max(
    dp[i-1][k][1],
    dp[i-1][k][0] - prices[i]
)

为什么是卖出时 k-1，而不是买入？
因为一次交易以“完成卖出”为标志。理论上由于最后一天不持有股票的价值一定最高，所以买入时进行 k-1 也可以。

121 / 123 与 188 的关系

六、加入约束三：手续费（714）

本质变化

每一笔交易都会多付出一个固定成本。

手续费只影响 买入或卖出其中一个时机，常见处理方式：

在买入时扣手续费

1
2
3
4

dp[i][1] = max(
    dp[i-1][1],
    dp[i-1][0] - prices[i] - fee
)

或在卖出时扣手续费（等价）

1
2
3
4

dp[i][0] = max(
    dp[i-1][0],
    dp[i-1][1] + prices[i] - fee
)

七、状态机 DP 的工程级总结

建模顺序

1. 时间轴是什么？（天数 / 下标）
2. 系统有哪些有限状态？（股票的持有与否）
3. 哪些状态之间可以互相转移？（持有股票通过当天卖出转化为未持有）
4. 哪些转移有额外约束？（手续费、交易次数限制）

股票状态机的通用模板

1
2
3
4
5

for i in [0..n):
    for state in States:
        dp[i][state] = max(
            from all valid prev_state
        )

状态机 DP 变形

• 可迁移到时机开发中：订单状态流转、流控 / 限流、工作流引擎、资源占用 / 释放建模

这是后端系统里“时间 + 状态”的通用建模方式。

相关代码

本文涉及的所有代码与笔记，均已同步至我的 GitHub 算法仓库，作为 Java 后端校招过程中的学习记录。

本文以一个前后端分离的 Spring Boot 后端项目为背景，系统梳理了从Nginx 反向代理与负载均衡、登录鉴权、接口文档、员工模块开发到异常处理、拦截器、ThreadLocal、分页查询等高频后端知识点

一、Nginx：反向代理与负载均衡

1. 为什么前端请求能“自动”到后端？

前端请求地址：

1

http://localhost/api/employee/login

后端真实接口：

1

http://localhost:8080/admin/employee/login

中间桥梁：Nginx 反向代理

2. 什么是反向代理？

反向代理是由服务器端统一接收客户端请求，再转发给内部真实服务，对客户端屏蔽后端细节。

工程层面的价值：

• 统一入口：前端永远只访问 Nginx
• 解耦前后端端口与路径
• 安全隔离：后端服务不直接暴露
• 性能优化：支持缓存、压缩、限流

3. proxy_pass 核心配置理解

1
2
3
4
5
6
7
8

server {
    listen 80;
    server_name localhost;

    location /api/ {
        proxy_pass http://localhost:8080/admin/;
    }
}

/api/ + /admin/ 是怎么拼接的？

核心规则

当 location 和 proxy_pass 都以 / 结尾时：

Nginx 会用 proxy_pass 中的路径，替换掉 location 匹配到的那一段路径

请求 URL：

1

/api/employee/login

location 命中部分：

1

/api/

剩余路径：

1

employee/login

proxy_pass：

1

http://localhost:8080/admin/

最终转发到后端的真实请求：

1

http://localhost:8080/admin/employee/login

不是拼接，而是「替换 + 保留剩余路径」

“Nginx 是怎么知道 employee/login 要保留的？”
location 匹配到的部分会被去掉，没有匹配到的剩余路径拼接到 proxy_pass 的路径后。

proxy_pass 结尾是否带 / 的区别

情况 1：proxy_pass 带 /

1
2
3

location /api/ {
    proxy_pass http://localhost:8080/admin/;
}

替换路径

1

/api/xxx  →  /admin/xxx

最常用、最推荐

情况 2：proxy_pass 不带 /

1
2
3

location /api/ {
    proxy_pass http://localhost:8080/admin;
}

直接拼接完整 URL

1
2
3

/api/employee/login
↓
http://localhost:8080/admin/api/employee/login

小结

Nginx 是七层代理还是四层代理？

这里是 HTTP 七层代理

为什么是七层？

当前使用的是：

1

proxy_pass http://...

并且：

• Nginx 能看到：

  URL 路径（/api/employee/login）

  HTTP 方法（GET / POST）

  Header

  Cookie

• 能基于 URI / Header / Host 做路由

这说明它工作在 HTTP 层（应用层）

四层代理是什么样？

如果是四层代理（TCP）：

1
2
3
4
5
6

stream {
    server {
        listen 3306;
        proxy_pass mysql_backend;
    }
}

• 不关心 HTTP
• 不解析 URL
• 只转发 TCP 流量

总结

二、Nginx 负载均衡

本质认知

负载均衡 = 基于反向代理的请求分发策略

1
2
3
4
5
6
7
8

upstream webservers {
    server 192.168.100.128:8080;
    server 192.168.100.129:8080;
}

location /api/ {
    proxy_pass http://webservers/admin;
}

常见负载均衡策略

注意：
ip_hash 并不能解决分布式 Session 问题，只能缓解。

三、登录功能设计（JWT 是重点）

为什么不用 Session？

HTTP 无状态 + 分布式部署的情况下：Session 粘性差 （），所以 JWT 更适合前后端分离

登录整体流程

1. Controller 接收 DTO
2. Service 校验用户：用户是否存在、密码是否匹配、状态是否禁用
3. 生成 JWT → 返回给前端
4. 前端后续请求在 Header 中携带 token

JWT 核心组成

• Header：算法
• Payload：用户信息（如 employeeId）
• Signature：密钥签名
• 关键属性：secretKey、expireTime

注意：

JWT 的 Payload 只是经过 Base64URL 编码而非加密，任何人都可以解码查看其中内容，因此不应在载荷中存放密码、身份证号等敏感信息，仅保留必要的业务标识字段。

四、密码安全

为什么不能明文存储？

• 数据库泄露 = 全员密码泄露
• 不符合基本安全规范

当前方案

• 注册 / 新增员工：MD5 加密后存储
• 登录：明文 → MD5 → 对比

后续可拓展：

• MD5 不安全 → BCrypt / Argon2
• 是否加盐？在对用户密码做哈希之前，先拼接一段随机字符串（salt），再进行哈希（TODO）。
• 登录失败次数限制

五、接口文档体系（Swagger vs YApi）

两者定位区分（高频）

YApi 管设计，Swagger 管实现。

Knife4j 配置要点

• Docket Bean
• Controller 扫描路径
• 静态资源映射

六、员工模块开发（CRUD 模板）

通用开发流程

1. 接口设计（路径 / 方法 / 参数）
2. DTO 设计
3. Controller
4. Service 接口
5. Service 实现
6. Mapper + XML
7. 测试

七、JWT 拦截器（高频 + 易追问）

拦截器职责

• 获取 token
• 校验 token
• 解析用户 ID
• 放行 / 拒绝

preHandle 核心逻辑

1
2
3

String token = request.getHeader("token");
Claims claims = JwtUtil.parseJWT(secretKey, token);
Long empId = Long.valueOf(claims.get("empId").toString());

• token 过期会发生什么？解析失败，不会返回 claims，直接抛异常，视为 token 校验失败
• 401 vs 403 区别？401 未认证/认证失败；403 已认证但无权限
• 拦截器 vs 过滤器？过滤器是 Servlet 规范，拦截器是 Spring MVC 机制，拦截器更贴近 Controller。

八、ThreadLocal

ThreadLocal 为每个线程提供独立变量副本，避免并发冲突。

在本项目中的作用

• 拦截器中存用户 ID
• Service / Mapper 统一获取
• 自动填充：create_user 、update_user

拓展：

• ThreadLocal 内存泄漏？线程池复用，同时没有及时删除 ThreadLocal 中的值
• 为什么要 remove？避免线程复用时脏数据串请求，同时防止线程长期持有 value 导致OOM。
• 在 Tomcat 线程池中的问题？Tomcat 使用线程池复用线程，ThreadLocal 的生命周期会被“线程生命周期”拉长，如果不清理会导致数据跨请求污染和内存滞留。

九、全局异常处理

为什么要全局异常处理？

• Controller 不关心异常细节
• 统一返回格式
• 防止异常信息直接暴露

重复用户名异常处理

1

@ExceptionHandler(SQLIntegrityConstraintViolationException.class)

十、分页查询（PageHelper）

PageHelper 核心思想

拦截 SQL → 自动拼接 limit

1

PageHelper.startPage(page, pageSize);

返回结构设计

1

total + records

拓展：

• PageHelper 原理？通过拦截 SQL 执行，在原 SQL 基础上自动拼接分页语句（limit / count），并利用 ThreadLocal 传递分页参数。（count 用于返回总记录数）
• 与 MyBatis Plus 区别？PageHelper 是 MyBatis 插件、对 SQL 无侵入；MyBatis Plus 是 ORM（Object–Relational Mapping，对象关系映射：把数据库表映射为程序中的对象、把 SQL 操作映射为对象方法调用的技术。） 增强框架，分页是其内置能力。
• 大数据量分页优化？利用子查询+索引覆盖/游标/延迟关联

十一、统一更新时间格式（细节加分）

• 扩展 Spring MVC 消息转换器
• 全局 Date / LocalDateTime 处理
• 避免前后端时间不一致问题

十二、分类模块删除约束

不能删除仍被引用的数据

• 分类 → 菜品 / 套餐
• 删除前先校验
• 有关联 → 抛业务异常

总结

这个项目完整覆盖了后端环境搭建、网关层设计、鉴权体系、异常体系、分页机制与业务约束设计，不仅实现功能，更体现了真实生产级后端的工程思维。

学习资料与完整代码

已整理并上传至 GitHub 仓库

本文基于一个真实后端业务系统（Spring Boot + MyBatis）的实现过程，系统性总结了三个实际开发中遇到的问题：公共字段填充、文件上传服务设计、多表业务模块实现。

一、公共字段自动填充：用 AOP 解耦“横切逻辑”

问题背景（Why）

在一个标准的后端系统中，几乎所有业务表都会包含以下公共字段：

如果在每个 insert / update 的 Mapper 方法中手写赋值逻辑，会带来三个问题：

1. 重复代码严重
2. 业务代码被污染
3. 容易遗漏或写错

这是一个非常典型的 横切关注点（Cross-Cutting Concern）。

设计目标

从工程角度，我希望这个功能满足：

• 业务代码 零侵入
• 插入 / 更新行为 语义清晰
• 能够 统一治理、集中维护

因此选择方案是：

Spring AOP + 自定义注解

实现方案概述

整体设计拆分为三层职责：

1. 注解层：声明“这个方法需要自动填充”
2. 切面层：统一拦截、统一处理
3. 实体层：通过反射注入公共字段

核心实现解析

（1）自定义注解：表达“意图”

1
2
3
4
5

@Target(ElementType.METHOD)
@Retention(RetentionPolicy.RUNTIME)
public @interface AutoFill {
    OperationType value(); // INSERT / UPDATE
}

关键点：

• 不关心“填充什么字段”
• 只关心“这是一次什么操作”
• 将 业务语义 与 实现细节 完全解耦

（2）切面设计：拦截 + 分类处理

1
2

@Pointcut("execution(* com.sky.mapper.*.*(..)) && @annotation(com.sky.annotation.AutoFill)")
public void autoFillPoinCut() {}

• 只拦截 Mapper 层
• 只拦截显式声明了 @AutoFill 的方法
• 避免 误伤 / 全局污染

（3）前置通知：为什么是 @Before？

1
2

@Before("autoFillPoinCut()")
public void autoFill(JoinPoint joinPoint) { ... }

原因很简单但很关键：

公共字段必须在 SQL 执行之前完成赋值，否则 ORM 层拿到的是脏数据。

（4）反射注入字段

1
2

Method setCreateTime = entity.getClass()
    .getDeclaredMethod("setCreateTime", LocalDateTime.class);

拓展问题

• 为什么不用接口？
• 为什么不用父类？
• 如果实体不包含这些字段怎么办？

答：

• 因为这是内部约定型的横切逻辑，不需要多态，接口会增加侵入性和实现成本。如果做成通用框架或给第三方用，才会考虑接口约束。
• 父类会强制所有实体继承，破坏领域模型独立性，而 AOP + 反射只对“需要的地方”生效，更灵活。
• 可以加字段存在性校验并抛异常。

二、文件上传服务：从“能用”到“可扩展”

存储方案对比（Why）

在实际项目中，选择的是：

云厂商 OSS（阿里云 OSS ）

OSS 上传整体流程

实现关键点

（1）密钥安全

• 使用 RAM 子账号
• 通过 环境变量 注入 AccessKey
• 不写死、不提交到仓库

1
2

setx OSS_ACCESS_KEY_ID "xxx"
setx OSS_ACCESS_KEY_SECRET "xxx"

（2）配置解耦

• YAML 配置
• @ConfigurationProperties 注入
• 工具类 + Spring 管理

这说明你理解：

配置 ≠ 代码

（3）上传核心逻辑

1
2
3
4
5

ossClient.putObject(
    bucketName,
    objectName,
    new ByteArrayInputStream(bytes)
);

在这里你做的是：

• 将 I/O 细节 封装在基础设施层
• Controller 只负责 接收请求与返回结果

拓展问题

• 如何避免文件名冲突？
• 如何做断点续传？
• 如何限制文件类型 / 大小？

答：

• UUID+随机数
• 采用 分片上传，每个分片单独上传并记录状态，失败只重传缺失分片，最终由 OSS 合并。
• 后端校验 Content-Type、文件大小，并做必要的内容校验

三、菜品管理模块：典型多表业务设计

DTO / VO 分离

• DTO：接收请求
• Entity：数据库映射
• VO：返回前端

当实体类与请求参数相差较大时，需要引入 DTO；同时返回数据与实体类相差较大时，引入 VO

主从表插入

1

<insert useGeneratedKeys="true" keyProperty="id">

• 先插主表
• 拿主键
• 再批量插从表

1

<foreach collection="flavors" item="df" separator=",">

删除逻辑：业务约束优先于数据库

• 起售中的菜品不能删除
• 不是靠外键
• 而是靠 业务校验 + 自定义异常

数据库外键 ≠ 业务约束

更新策略：先删后插

1
2
3

update dish
delete flavors
insert flavors

• 简化逻辑
• 保证一致性
• 配合事务使用

学习资料与完整代码

已整理并上传至 GitHub 仓库

基础题目：300. 最长递增子序列
扩展题目：354. 俄罗斯套娃信封问题

一、引言：LIS 在「线性 DP」中的位置

在完整学习了：

• 打家劫舍（选 / 不选）
• 爬楼梯（排列计数）
• 背包问题（容量约束）
• 双序列线性 DP（公共子序列）

之后，最长递增子序列（LIS）是线性 DP 中最后、也是最容易“升维”的一种模型。

它的核心特征非常明确：

单序列 + 子序列 + 有序性约束

一旦理解 LIS，不仅可以解决一维问题，还可以通过排序 + 降维，解决看似更复杂的二维、分组问题。

二、354. 俄罗斯套娃信封问题

问题本质与第一直觉

每个信封用 (w, h) 表示，若：

1

w1 < w2 且 h1 < h2

则信封 1 可以嵌套进信封 2。

直觉思路是：

把每个信封当成一个“元素”，求最长递增子序列

但这里存在一个关键陷阱：

题目允许任意重排信封顺序
→ 原数组顺序是无意义的
→ 直接在二维数组上做 LIS 会漏解

正确建模：二维 → 一维的关键转化

要想使用 LIS，必须满足：

只在一个维度上递增

因此需要先消除一个维度的干扰。

核心转化步骤

Step 1：排序

• 宽度 w：升序
• 高度 h：降序（当 w 相同）

1
2
3
4
5
6
7

// 双关键字排序：宽度升序，高度降序
Arrays.sort(envelopes, (a, b) -> {
    if (a[0] == b[0]) {
        return b[1] - a[1]; // 高度降序
    }
    return a[0] - b[0];     // 宽度升序
});

为什么 w 相同时要按 h 降序？

这是本题最容易被忽略、也是面试最常考的点。

如果：

• w 相同
• h 也按升序排

那么在之后对 h 求 LIS 时，会错误地把同一宽度的信封选进子序列，违反题意（宽度必须严格递增）。

而 h 降序 的作用是：

在 LIS（严格递增）中，相同 w 的信封不可能同时被选中

问题彻底降维：只看高度 h

排序完成后：

• 宽度已经隐式满足递增约束
• 只需要在高度数组上求 严格递增 LIS

问题就完全转化为：

300. 最长递增子序列

算法复杂度分析

• 排序：O(n log n)
• LIS（贪心 + 二分）：O(n log n)

整体复杂度：

1

O(n log n)

满足 n ≤ 10^5 的数据规模要求。

三、心得体会（俄罗斯套娃 → LIS）

这道题真正考察的不是 LIS 本身，而是问题转化能力：

1. 是否意识到原顺序无意义
2. 是否能通过排序消掉一个维度
3. 是否处理了“相等元素”的边界情况

本质模型可以总结为一句话：

二维严格递增问题 = 排序 + 一维 LIS

四、线性 DP 模型全景总结

回顾整个线性 DP 学习路径，可以清晰地分为 五大模型。

打家劫舍模型（选 / 不选 + 相邻约束）

核心特征

• 枚举元素选或不选
• 相邻元素不能同时选

典型变形

• 打家劫舍 II（成环）
  → 拆成「选第一个 / 不选第一个」
• 删除并获得点数
  → 构造值域数组，转化为打家劫舍

爬楼梯模型（排列型 DP）

核心特征

• 顺序不同 = 不同方案
• 每一步选择不同“动作”

常见变形

• 最小代价爬楼梯
• 目标字符串构造方案数
• 组合总和（顺序相关）
• 分组 + 爬楼梯

背包模型（容量约束）

分类

• 01 背包（不能重复选）
• 完全背包（可以重复选）

常见问法

• 至多 / 恰好 / 至少装满
• 求最大值 / 最小值 / 方案数

重要收获

• 空间优化的本质：

  明确当前状态依赖哪些旧状态

  是否会发生状态覆盖

  必要时引入 pre

双序列线性 DP

核心特征

• 操作两个序列
• 关注“公共部分”

典型问题

• 最长公共子序列（LCS）
• 最短公共超序列（SCS）
• 编辑距离

最长递增子序列（LIS）

核心特征

• 单序列
• 子序列
• 有序性约束（递增 / 非递减）

两种解法层级

关键技巧

交换 dp 的“状态”与“状态值”

• 用 g[k] 表示：
  • 长度为 k+1 的递增子序列
  • 其末尾元素的最小值

严格来说：

• g 不存在状态覆盖
• 已不再是传统 DP
• 而是 贪心 + 有序结构 + 二分查找

相关代码

本文涉及的所有代码与笔记，均已同步至我的 GitHub 算法仓库，作为 Java 后端校招过程中的学习记录。

基础题目：300. 最长递增子序列

扩展题目：

• 将三个组排序
• 找出到每个位置为止最长的有效障碍赛跑路线
• 得到山型数组的最少删除次数
• 使数组 K 递增的最少操作次数

一、概述：为什么 LIS 是一种“新的线性 DP”

这两天的题目有一个非常鲜明的共同点：

都是「单数组 + 子序列 + 有序性」问题

它们与之前接触的模型（如 0/1 背包、完全背包、双序列 DP）有本质区别：

• 不是选容量 / 次数
• 不是两个序列之间的匹配
• 而是：在保持原相对顺序的前提下，选出一个“有序的子序列”

这类问题的核心关键词是：

• 子序列（Subsequence）
• 递增 / 不降（有序性约束）
• 最长 / 最少删除（等价转化）

而这一整类问题，几乎都可以归约到一个经典母题：

最长递增子序列（LIS）

二、300. 最长递增子序列（LIS）

从回溯到 O(n²) 线性 DP

思维起点：子序列 = 子集的一种

LIS 本质是一个「选或不选」的问题，可以有两种回溯视角：

• 枚举元素选不选
  → 需要额外维护「上一个选了谁」
• 枚举答案以谁结尾（更适合 DP）
  → 只关心：以 nums[i] 结尾的 LIS 最长是多少

状态定义

1

dp[i]：以 nums[i] 结尾的最长严格递增子序列长度

状态转移

1

dp[i] = max(dp[j] + 1)  (j < i 且 nums[j] < nums[i])

复杂度

• 状态数：n
• 转移代价：n
• 时间复杂度：O(n²)

考虑优化时间复杂度。

贪心 + 二分：从 O(n²) 到 O(n log n)

当 n 上到 10⁵ 时，O(n²) 就不够用了，需要进一步优化。

核心技巧只有一句话：

将 dp 的「状态」和「状态值」进行交

关键构造：g 数组

我们不再显式记录「每个位置的 LIS 长度」，而是维护一个数组：

1

g[k]：长度为 k+1 的递增子序列，其末尾元素的最小可能值

它有两个重要性质：

• g 始终是单调递增的
• g.size() 就是当前 LIS 的长度

遍历过程（贪心本质）

对每个元素 x = nums[i]：

1. 在 g 中二分查找：
   • 严格递增 LIS：找第一个 >= x 的位置
2. 分两种情况：
   • 找不到（位置 == g.size）
     → 说明可以扩展长度，g.add(x)
   • 找到了
     → 用 x 替换该位置，g[pos] = x

为什么可以替换+为什么要替换

因为：

• 我们只关心 在固定长度下，末尾元素越小越好
• 更小的末尾元素，能给后续元素留下更大的扩展空间

这就是贪心正确性的核心。

时间复杂度：O(n log n)

三、LIS 的“模型迁移”：扩展题统一视角

2826. 将三个组排序

核心转化：

• 不要求严格递增
• 只要求 非递减子序列

问题等价于：

1

最少操作数 = n - 最长非递减子序列长度

实现细节：

• 二分时找 第一个 > x 的位置

1964. 有效障碍赛跑路线

题目要求的是：

到每个位置为止的最长非递减子序列长度

关键点：

• g 数组的维护方式不变
• 每次插入 / 替换后：当前 g.size() 就是答案，因为遍历nums的过程，每个数都对应一次操作。

本质是 LIS 贪心过程的“在线版本”

1671. 得到山型数组的最少删除次数

标准「山型数组」模型：

• 枚举 i 作为峰顶
• 左边：最长严格递增子序列
• 右边：最长严格递减子序列

处理技巧：

• 右侧「严格递减」
  → 倒序遍历，等价于再做一次 LIS

答案计算：

1

n - (len_left + len_right - 1)

注意边界：

• 峰顶左右必须至少有一个元素 → len_left >= 2 && len_right >= 2

2111. 使数组 K 递增的最少操作次数

核心拆解：

1. 按下标 i % k 分成 k 组
2. 每一组 互不影响
3. 对每一组：
   • 求最长非递减子序列长度

最终答案：

1

总长度 - 各组 LNDS 之和

这是一个非常经典的：

“全局问题 → 独立子问题 → LIS 统一求解”

四、方法论总结

子序列 + 最少操作 = 最长子序列

只要题目满足：

• 只能删除 / 修改
• 不改变相对顺序

几乎都可以转化为：

1

最少操作 = n - 最长满足条件的子序列长度

严格递增 vs 非递减（二分差异）

这是 LIS 题中最容易写错的点

为什么 LIS 属于线性 DP

• 本质仍是 DP
• 只是通过：
  • 贪心
  • 有序结构
  • 二分查找
• 将状态转移从 O(n) 优化成 O(log n)

这个优化的关键技巧只有一句话：

交换 dp 的“状态”和“状态值”

五、总结

300. 最长递增子序列（LIS）是一个“母题”：

• 它不是一题，而是一整类题型的统一入口

• 一旦 LIS 的 O(n²) 与 O(n log n) 两套思路真正吃透：

  • 山型数组

  • 非递减序列

  • 分组 LIS

  • 最少删除 / 修改问题

都可以自然转化、快速识别

相关代码

本文涉及的所有代码与笔记，均已同步至我的 GitHub 算法仓库，作为 Java 后端校招过程中的学习记录。

本文通过 1143、72、583 三道典型题目，总结出线性 DP 的核心不在于「一维还是二维」，而在于当前状态只依赖于“更小规模的历史状态”，并且状态推进顺序是线性的；字符串 DP 与背包 DP 在模型上是统一的，只是状态含义不同。

一、什么是「线性 DP」——不是维度，而是递推方向

最初我把“线性 DP”理解为一维数组，但这其实是结果，不是本质。

1. 状态只依赖于“过去”

• dp[i] 或 dp[i][j] 只从更小的 i / j 推导
• 不存在回头依赖、环形依赖

2. 状态推进顺序是线性的

• 一维：i = 1 → n
• 二维：固定一个维度，另一个维度线性推进
  （例如先枚举 i，再枚举 j）

3. 可以被空间优化（但不是必须）

• 如果 dp[i] 只依赖 dp[i-1]，就能压缩
• 如果 dp[i][j] 只依赖上一行或左侧，也可以压缩

是否能压缩 ≠ 是否是线性 DP

二、统一视角：字符串 DP 与背包 DP 本质相同

01 背包、完全背包、LCS、编辑距离，本质上都是“位置 + 决策”的线性 DP。

三、经典模型一：1143 最长公共子序列（LCS）

状态定义

dp[i][j]：
word1 前 i 个字符 与 word2 前 j 个字符 的最长公共子序列长度

注意：

• 是「前 i 个」，不是「第 i 个」
• 这是为了让 dp[0][*] 成为合法边界

决策拆解（从 DFS 到 DP）

站在回溯角度：

• 当前考察 word1[i-1] 和 word2[j-1]
• 两种情况：
  • 相等 → 一起加入子序列
  • 不等 → 放弃其中一个

状态转移（核心）

1
2
3
4

if word1[i-1] == word2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

这是一个非常“干净”的线性 DP：

• 依赖方向：左、上、左上
• 遍历顺序：i 从小到大，j 从小到大

四、经典模型二：72 编辑距离（Edit Distance）

状态定义

dp[i][j]：
word1 前 i 个字符 转换为 word2 前 j 个字符 的最少操作数

为什么它和 LCS 是同一类问题？

可以从“操作视角”统一理解：

其中：

• cost = 0（字符相等）
• cost = 1（字符不等）

状态转移方程

1
2
3
4
5
6
7
8

if word1[i-1] == word2[j-1]:
    dp[i][j] = dp[i-1][j-1]
else:
    dp[i][j] = min(
        dp[i-1][j],     // 删除
        dp[i][j-1],     // 插入
        dp[i-1][j-1]    // 替换
    ) + 1

和 LCS 的区别不在于 DP 框架，而在于：

• 相等时是否“奖励 +1”
• 不等时是取 max 还是 min

五、模型变形：583 两个字符串的删除操作

这道题是 编辑距离的特例：

• 只能删除
• 允许对两个字符串都删除

两种等价解法（体现思维深度）

解法一：直接 DP（编辑距离删减版）

• 只保留「删除」相关转移
• 不允许插入和替换

解法二：LCS 转化（更优雅）

1
2

最少删除次数 =
    len(word1) + len(word2) - 2 * LCS(word1, word2)

六、字符串 DP vs 背包 DP：本质对比总结

七、总结

• 线性 DP 的核心是 “状态规模单调变小 + 线性遍历顺序”
• LCS、编辑距离、字符串删除问题 本质是一套 DP 模型
• 能从 DFS → 状态定义 → 转移方程 → 空间优化，是完整 DP 能力的体现
• 理解状态含义，比记公式重要得多

相关代码

本文涉及的所有代码与笔记，均已同步至我的 GitHub 算法仓库，作为 Java 后端校招过程中的学习记录。

本文是在学习过程中，零星对 git 的学习的总结与汇总。

什么是 Git

git 是基于 c 语言的分布式版本控制系统，与之对应的是集中式版本控制系统。这两者的不同：

• 集中式版本控制系统：版本库存放在中央服务器，必须联网才能从中央服务器拉取最新版本，推送新版本到中央服务器。
• 分布式版本控制系统：没有中央服务器，每个人的电脑都有一个完整的版本库。多人协作的实现是通过将各自修改的内容推送给对方。实际应用中，通常用一台电脑充当“中央服务器”，这个服务器只用来交换大家的修改信息，不存放版本库。

git 的优势不单单是不必联网，还有强大的分支管理

版本库

版本库又名仓库（Repository），可以理解为一个目录，这个目录中的所有文件受 git 管理，每个文件的增删改，git 都能跟踪，以便根据需求还原。

创建版本库非常简单，在需要交给 git 管理的目录下，执行 git init 命令即可。

需要注意的是，目录名尽量不要包含中文。

所有的版本控制系统，其实都只是跟踪文本文件的改动，例如 txt 文件、程序代码等等，不能监控图片、视频这种二进制文件（只能监控大小的改变，内容的改变不能监控）。

添加文件到版本库

在 git 管理的目录下，通过 git add <filename> 添加文件到版本库，再通过 git commit -m "msg" 命令把文件提交到仓库。git status 命令可以查看仓库当前状态，会提示修改过的文件，以及准备提交的文件（add 的文件）。git diff 命令可以对比文件哪些地方变化了。

注意添加和提交是两个操作。

小结（目前最常用命令）

• git init：将当前目录交给 git 管理
• git add <filename>：将指定文件添加到版本库中
• git commit -m "msg"：提交本次修改，msg 是对本次提交的说明
• git status：查看仓库当前状态，哪些文件被修改了，哪些文件添加到版本库中但是还没有提交
• git diff：查看文件修改内容

时光穿梭

版本回退

同一仓库，经过多次提交后，难免记不清哪个版本修改了什么内容，所以在进行版本回退前，可以通过 git log 命令查看历史记录，可以看到包含了每次提交的 commit id：364… 以及谁提交的，以及日期和每次提交的说明。

此外，我们还需要当前版本的信息，head 指向的就是当前版本，然后就可以定位需要回退的版本，通过 git reset 命令进行回退

1

git reset --hard HEAD^

^ 表示上个版本，多个版本可用 ， HEAD100 表示回退 100 个版本。

–hard 参数表示回退上个版本的已提交状态，–soft 表示回退到上个版本的未提交状态，–mixed 回到上个版本已添加但是为提交的状态。

也可以通过 git reset --hard f35ed 回退到具体版本，或者穿梭到未来的版本，注意这里 commit id 不用写全，只要让 git 能够找到唯一的版本即可。git reflog 命令显示 git 记录的每一次命令，通过这个可用查看版本号。

git 的版本回退速度非常快，因为 git 内部有个指向当前版本的 HEAD 指针，回退版本时，仅仅是将 HEAD 指向指定版本

小结

• git reset --hard HEAD^/指定版本号：回退到当前版本的上个版本或回退到指定版本号的版本
• git log 与 git reflog ：命令查看历史记录，来找到需要回退的版本或版本号

工作区与暂存区

工作区，就是电脑中实际操作的目录。

版本库，是工作区中的隐藏目录 .git，其中存储 git 进行版本控制的很多信息，最重要的就是暂存区（stage）和 git 自动创建的 master 分支，以及指向 master 分支的 HEAD 指针。

• git add 就是将文件修改添加到暂存区
• git commit 就是将暂存区的所有内容添加到当前分支

可以理解为：需要提交的文件修改通通放到暂存区，然后，一次性提交暂存区的所有修改。

管理修改

git 管理的是对文件的修改而非文件，怎么理解？例如，在文件中新增一个 ‘a’ 字符，然后 git add 后又将字符改为了 ‘b’，暂存区中只知道你将新增了一个字符 ‘a’，而不知道它改为了 ‘b’，这是一个很好的证明 git 管理的是修改而非文件本身。

撤销修改

撤销修改有三种情形：

• 只是对工作区进行了修改，还没有 add 与 commit：直接通过 git restore <file> 撤销修改

• 对工作区的修改，添加到了暂存区：通过 git restore --staged <file> 命令将文件从暂存区删除，然后通过 git restore <file> 撤销修改。

• 对工作区的修改不仅添加到了缓存区，还提交到了分支当中：git reset HEAD^ 进行版本回退。

git checkout –filename 命令是让文件回到最近一次 add 或 commit 时的状态

文件的删除

仓库中的文件的删除也是一次修改操作，git 会记录下来。如果想在 git 仓库中也实现文件的永久删除，可以用 git rm filename 命令，也可以用 git add filename 将这次修改提交到暂存区，然后再提交。

如果要撤销这次删除操作，只需要用到上一节介绍的 git checkout --filename 命令

这里需要注意的就是：没有被添加到仓库中的文件，git 是无法控制的

远程仓库

以上的功能，集中版本控制系统也能做到。真正体现 git 优势的是远程仓库，简单来说，就是将本地仓库托管到服务器上每天 24 小时开机，也可以从服务器中拉取别人的仓库，还能将提交推送到服务器上。

GitHub 就是提供 Git 仓库托管服务的，你需要告诉远程仓库你的身份信息，谁都可以修改你的远程仓库。本地Git仓库和 GitHub 仓库之间的传输是通过 SSH 加密的，所以需要先设置 SSH 密钥。

添加远程库

在 github 上创建好远程仓库后，需要将它与本地仓库关联：

1

git remote add origin git@github.com:tingfeng-worK/project.git

如果没有设置 SSH 密钥这一步，本地推送就推送不到远程仓库，相当于没有登录。命令中的 origin 是默认的远程仓库名，将本地仓库的内容推送到远程仓库，用命令 git push，实际上是将当前分支 master 推送到远程库，第一次推送时需要加上 -u 参数，它表示 git 不但会把本地的 master 分支推送到远程库中新的 master 分支，还会将它们关联起来，以后推送或拉取时就可以简化命令。

1

git push -u origin master

从远程库克隆

上述添加远程库是将本地已有的仓库添加并关联到远程仓库，而将远程仓库拉取到本地用到的 git 命令是：

1
2
3

git clone git@github.com:tingfeng-worK/project.git # ssh 协议

git clone https://github.com/tingfeng-work/project.git # https 协议

Git 支持多协议，可以使用 https，但是使用 ssh 最快

分支管理

Git 的分支管理是它的优势之一，无论创建、切换和删除分支，Git在1秒钟之内就能完成！无论你的版本库是1个文件还是1万个文件。

分支管理就好比在一个项目中，你与队友并行在不同的分支上开发不同的功能，在这个分支上你想提交就提交，不会影响主分支，在功能完成后，将分支合并到主分支上，项目就同时具备了你俩开发的功能。

分支的创建与合并

每次提交，git 都会 将它们串联为一条时间线，这个时间线就是一个分支，目前为止用到的都是 git 默认为我们常见的主分支 master，HEAD 严格来说不是指向提交，而是指向 master，而 master 指向每一次提交，如图所示：

每次提交，master 分支都会向前移动一次，HEAD 指针也随之移动。

当我们创建新的分支 dev 时，相当于创建了一个新的时间线，Git 会创建一个 dev 指针，指向 master 相同的提交，再把 HEAD 指向 dev，就表示当前分支在 dev 上：

这也解释了为什么 git 新建分支很快，它只是新建了一个指针，同时更改了 HEAD 的指向。现在对工作区的修改提交之后，就是 dev 指针移动，而 master 指针不变了：

在dev上的工作完成后，就可以把dev合并到master上。这种单时间线的合并最简单，就是直接把master指向dev的当前提交，就完成了合并。相关指令：

• git branch：查看有哪些分支
• git branch <name> ：新建分支
• git checkout <name> 或 git switch <name>：切换分支
• git checkout -b <name> 或 git switch -c <name>：创建并切换到新建的分支
• git merger <name>：合并某分支到当前分支
• git branch -d <name>：删除分支

冲突解决

上面描述最简单的单时间线的分支合并，考虑合并两个时间线的分支，这种情况下，git 无法执行快速合并，只能试着把各自的修改合并起来：

但是，这种合并可能会有冲突，假设这两次提交针对文件的同一地方进行了修改，合并分支时就会产生冲突，这也很好理解，git 不知道到底要怎么修改，所以必须手动解决冲突后再提交，也就是明确告诉 git 要怎么改。手动解决后，再合并就会变为：

可以看到这种合并会创建一次新的提交，这也很好理解，因为这是对文件的一次修改。

• git log --graph --pretty=oneline --abbrev-commit：可以看到分支合并情况。

多人协作

• 从远程仓库拉取分支进行本地修改
• 修改后从本地推送分支，如果推送失败，说明远程仓库中已经有人对操作 1 中拉取的分支进行了修改，并提交到远程仓库了，这时需要需要进行合并。
• 如果合并失败，就在本地解决冲突，然后再提交。

这个过程会用到的指令：

• git remote -v：查看远程仓库信息

• git pull：拉取并合并远程基于当前分支的提交，这个命令执行的前提是远程仓库上的分支与当前分支建立了联系。

• git branch --set-upstream-to <branch-name> origin/<branch-name>：将远程仓库中的分支与本地分支建立联系

• git push origin <branch-name>：从本地推送分支到远程仓库

• git checkout -b branch-name origin/branch-name

Rebase

将本地未 push 的分叉提交历史整理为一条分支（一条直线）

标签

标签就相当于一个有名字的不会动的指针，指向某一个 commit，方便进行版本控制。如果没有标签，想要跳转到指定的版本，需要通过 git log 找 commit 的 id，而且 id 还很长，所以标签就起到了快速找到指定版本的作用。

创建标签

切换到需要打标签的提交，通过 git tag <name>，就实现打标签了，也可以指定 commit id 的方式打标签，同时指定 git tag -a <name> -m "msg" 参数可以对创建标签进行说明。git tag 查看所有标签，git show <tagname>查看指定标签。

注意：标签总是和某个commit挂钩。如果这个commit既出现在master分支，又出现在dev分支，那么在这两个分支上都可以看到这个标签。

操作标签

• 命令git push origin <tagname>可以推送一个本地标签；
• 命令git push origin --tags可以推送全部未推送过的本地标签；
• 命令git tag -d <tagname>可以删除一个本地标签；
• 命令git push origin :refs/tags/<tagname>可以删除一个远程标签。

GitHub 开源项目

在 GitHub 上，利用 Git 强大的克隆和分支功能，可以实现自由参与各种开源项目了。

对于开源项目，先 fork 到自己的远程仓库，再从自己的远程仓库中克隆到本地仓库。对本地仓库的修改，再提交到自己的远程仓库，如果希望自己的修改被项目方接受，需要在 GitHub 上发起 pull request，最终取决于对方是否接受。

学习 Git 的网站

https://learngitbranching.js.org/?locale=zh_CN

本文通过 494、322、2915 三道典型题目，总结 0-1 背包与完全背包的统一建模方式。重点在于如何从回溯语义自然推导出动态规划模型。

基础题目：01背包、完全背包

01背包变形：

494.目标和、2915.和为目标值的最长子序列的长度

完全背包变形：

322.零钱兑换

一、为什么要从“回溯语义”入手理解 DP？

在学习动态规划的过程中，我一度陷入这样的问题：

• 明明知道这是 DP 题
• 但一到写 dp[i][j] 就容易：
  • 不知道从何下手
  • 理解错误状态含义
  • 写错初始化

后来我解题循序渐进旨在加深对回溯与DP的理解：

所有 DP 题，先用 dfs(i, j) 把“语义”想清楚，再翻译成 DP。

这篇博客正是围绕这一方法，总结 0-1 背包与完全背包 这两类最常见的 DP 模型。

二、统一视角：什么是“背包模型”？

从抽象层面看，背包问题的本质只有一句话：

枚举每个输入元素，决定“选或不选”，并维护一个容量约束。

0-1 背包模型

问题描述

• 有 n 个物品
• 第 i 个物品体积 w[i]，价值 v[i]
• 每个物品最多选一次
• 在容量 capacity 内，求最大价值和

回溯语义三问（非常重要）

• 当前操作：枚举第 i 个物品选或不选：不选，剩余容量不变；选，容量减少 w[i]
• 子问题：剩余容量为 c 时，前 i 个物品中的最大价值和
• 下一个子问题：分类讨论：
  • 当前操作不选：剩余容量 c 从前 i-1 个物品中得到的最大价值
  • 当前操作选：剩余容量 c - w[i] 从前 i-1 个物品得到的最大价值

回溯表达式

1
2
3
4
5
6
7
8
9
10

int dfs(int i, int c, int[] w, int[] v) {
    if (i < 0) return 0;
    if (w[i] > c) {
        return dfs(i - 1, c, w, v);
    }
    return Math.max(
        dfs(i - 1, c, w, v),                 // 不选
        dfs(i - 1, c - w[i], w, v) + v[i]    // 选
    );
}

一旦写出这段递归，DP 就已经成功了一半。

完全背包模型

完全背包与 0-1 背包只有一个本质区别：

当前物品是否允许在同一层决策中被再次使用

回溯表达式

1
2
3
4

dfs(i, c) = max(
    dfs(i - 1, c),          // 不选
    dfs(i, c - w[i]) + v[i] // 选，并且还能继续选 i
)

一个非常容易困惑的问题

为什么不需要写 dfs(i - 1, c - w[i])？即选了一次后不在选了

原因在于：

• dfs(i, c - w[i]) 中，下一层仍然可以选择“不选”，自然会递归到 dfs(i - 1, c - w[i])

也就是说：

“选一次就不再选”这个语义，已经被递归本身隐式表达了。

这是我在完全背包中收获最大的一个认知点。

三、常见背包问题的分类方式

在做题时，我会优先判断两个维度：

1. 装不装满？

• 至多装 capacity
• 恰好装 capacity
• 至少装 capacity

2. 求什么？

• 方案数
• 最大价值
• 最小价值

大部分 LeetCode 背包题，都可以被放入这个二维分类表中。

四、结合具体题目分析

494. 目标和 —— 0-1 背包（恰好装满，求方案数）

建模思路

• 每个数只能用一次 → 0-1 背包
• 每个数选或不选 → 枚举符号
• 本质是：恰好凑出 target 的方案数

回溯语义

1

dfs(i, t)：使用前 i 个数，凑出和为 t 的方案数

转移关系

1
2

dfs(i, t) = dfs(i - 1, t)           // 不选 nums[i]
          + dfs(i - 1, t - nums[i]) // 选 nums[i]

在实现时，我采用了：

1. 回溯 + 记忆化搜索
2. 翻译为二维 DP
3. 再做空间优化

这道题让我深刻体会到：
dp[i][j] 的含义，必须和 dfs(i, j) 的返回值一一对应。

322. 零钱兑换 —— 完全背包（恰好装满，求最小价值）

模型映射

为什么是完全背包？

因为：同一种硬币，在同一轮决策中可以被重复使用

转移方程（核心）—— 经过回溯、空间优化的结果

1
2
3
4

dp[j] = min(
    dp[j],              // 不使用当前硬币
    dp[j - coin] + 1    // 使用一次当前硬币
)

2915. 和为目标值的最长子序列 —— 0-1 背包（恰好装满，求最大价值）

抽象方式

• 每个元素只能选一次 → 0-1 背包
• nums[i] 作为“体积”
• 每选一个元素，价值 +1

语义定义

1

dp[j]：和为 j 时，能得到的最大长度

这道题让我意识到：

“价值”不一定是题目直接给的，而可以从题目中转化。

五、空间优化：理解即可，不必强求

在这三道题中，状态转移均只依赖于：

• 上一层 i - 1
• 或当前层更小的 j

因此可以：

1. dp[n][target] → dp[2][target]
2. 再进一步压缩为一维数组

但我目前的态度是：

空间优化属于锦上添花，优先保证语义正确。

如果一维 DP 的依赖方向一时想不清楚，我会选择保留二维。

六、总结与反思

通过这几道题，我对动态规划的理解有了一个明显转变：

• DP 的核心不在公式
• 而在 状态含义 + 转移语义

我目前仍然习惯：先写 dfs(i, j)，再翻译成 dp

但我也希望，随着练习的增多，能够逐渐做到：

• 直接从问题 → 状态定义 → 转移方程
• 减少对回溯的依赖

这是我接下来刻意训练的方向。

相关代码

本文涉及的所有代码与笔记，均已同步至我的 GitHub 算法仓库，作为 Java 后端校招过程中的学习记录。