前言

我将持续更新 yudao-vue-pro 芋道源码笔记，记录“全局架构 → 模块拆解 → 源码细节 → 最佳实践”的完整过程，每一步保留真实思考与踩坑记录，欢迎一起打卡。

为什么选它

1. 34.1k Star，社区体量足够，遇到问题能搜到现成讨论。** yudao-vue-pro 是 在 RuoYi-Vue 若依 基础上“二次开发”的社区版增强项目**
2. 官方把 RBAC、多租户、工作流、支付、短信、商城等模块做成可插拔 starter，不必自己补业务场景，直接调试即可。
3. 同一套后端接口同时供给 Vue3 管理端 + UniApp 小程序，前端部分可一次性验证 PC 与移动端，减少重复对接。

技术栈：Spring Boot、MyBatis Plus、Vue3、Element Plus、UniApp。
目标：借完整项目把后端零散知识串成体系，并夯实前端工程化能力。

本文从新增一个用户组功能开始作为入口来梳理下项目的结构和涉及到的前后端的功能模块。

新增用户组模块

下面简单列一下新增模块的过程，具体的可查阅网上相关资料。本文重点是来聊聊技术实现相关的内容。

第一步：数据库表设计

在数据库中设计 system_group 表，作为用户组模块的基础数据载体。

第二步：代码生成

进入管理后天台，先导入我们的设计表 system_group，然后在 “代码生成” 页面找到已设计好的 system_group 表，一鍵生成前后端代码和对应的 sql 文件。

第三步：代码复制与项目运行

将生成的代码分别复制到项目对应的目录中。

這是生成好的代码。将它们复制到对应的项目中进行运行。

运行成功后效果如下：

后端 yudao-module-system 目录结构

我们先从后端的项目代码来看起，首先来看看项目结构。这边仅列举了 yudao.module.system 包下的内容。这是本次新增用户组功能涉及到的模块。

cn.iocoder.yudao.module.system
├── api // 提供给其它模块的 API 接口（供其他模块/服务调用）
│   ├── dept        # 部门模块的服务间接口目录
│   │   ├── dto     # 服务间数据传输对象（DTO）目录
│   │   │   ├── DeptRespDTO.java  # 部门服务间响应 DTO，定义部门模块对外暴露的核心业务字段
│   │   │   └── PostRespDTO.java  # 岗位服务间响应 DTO
│   │   ├── DeptApi.java  # 部门服务间接口，定义部门模块可被外部调用的方法（如查询部门列表）
│   │   └── DeptApiImpl.java  # 部门服务间接口实现类，封装部门服务的调用逻辑（内部依赖 DeptService）
│   ├── ... // 其他业务模块的 api 目录
├── controller
│   ├── admin // 管理后台
│   │   ├── captcha
│   │   ├── dept
│   │   ├── dict
│   │   ├── group      # 你新增的用户组模块控制器目录
│   │   │   ├── vo     # 数据传输对象（DTO/VO）目录
│   │   │   │   ├── GroupPageReqVO.java  # 分页查询用户组的请求参数
│   │   │   │   ├── GroupRespVO.java     # 用户组详情的响应参数
│   │   │   │   ├── GroupSaveReqVO.java  # 新增/修改用户组的请求参数
│   │   │   └── GroupController.java     # 用户组模块的控制器（接口入口）
│   │   ├── ip
│   │   ├── logger
│   │   │   ├── dto     # 日志模块的请求/响应 DTO 目录（供 Controller 与 Service 交互）
│   │   │   │   ├── OperateLogPageReqDTO.java  # 操作日志分页查询请求 DTO
│   │   │   │   └── OperateLogRespDTO.java     # 操作日志响应 DTO
│   │   ├── mail
│   │   ├── notice
│   │   ├── notify
│   │   ├── oauth2
│   │   ├── permission
│   │   ├── sms
│   │   ├── social
│   │   ├── tenant
│   │   └── user
│   └── app // C端客户
│       ├── dict
│       ├── ip
│       └── tenant
├── dal // 数据访问层 Data Access Layer
│   ├── dataobject // 数据库实体对象（DO）目录,等同于 nest 中的 entity 
│   │   ├── dept
│   │   ├── dict
│   │   ├── group      # 用户组模块的数据库实体目录
│   │   │   └── GroupDO.java  # 系统用户组 DO，映射数据库表 `system_group`，封装用户组的基础字段（如ID、名称、状态等）
│   │   ├── logger
│   │   ├── mail
│   │   ├── notice
│   │   ├── notify
│   │   ├── oauth2
│   │   └── ... // 其他业务模块的 DO 目录
│   ├── convert // 数据对象转换工具（可选，用于 DO、VO、DTO 之间的转换）
│   ├── mapper // MyBatis 映射接口目录
│   ├── mysql // 数据库方言/特定实现目录（针对 MySQL 数据库的扩展）
│   │   ├── dict
│   │   ├── group      # 用户组模块的 MySQL 专属映射目录
│   │   │   └── GroupMapper.java  # 系统用户组 Mapper 接口，基于 MyBatis-Plus 实现数据库表 `system_group` 的 CRUD 操作，包含自定义分页查询等逻辑
│   │   ├── logger
│   │   ├── mail
│   │   ├── notice
│   │   ├── notify
│   │   ├── oauth2
│   │   ├── user
│   │   └── ... // 其他业务模块的 MySQL 专属 Mapper 目录
│   └── ... // 其他数据访问层组件（如 Repository）
├── service // 业务逻辑层
│   ├── group      # 用户组模块的业务服务目录
│   │   ├── GroupService.java  # 用户组业务接口，定义用户组的核心操作（新增、删除、查询、绑定用户等）
│   │   └── impl
│   │       └── GroupServiceImpl.java  # 用户组业务接口实现类，封装具体业务逻辑
│   └── ... // 其他业务模块的服务目录
├── enums // 枚举类目录
│   ├── group      # 用户组模块的枚举目录（可选，如用户组状态枚举 `GroupStatusEnum`）
│   └── ... // 其他业务模块的枚举

• api 是跨模块 / 服务的 “对外接口” ，供其他系统调用；
• service 是模块内的 “业务逻辑中心” ，供本模块的 Controller 调用；
• controller 是前端的 “入口” ，接收前端请求并调用 Service 处理。

Debug 执行流程

在新增完代码以后我们可以通过 Debug 模式启动 Java 项目，设置断点进行接口调试。我们从一次前端请求作为入口来说明整个调试的流程。

服务端可以简单分为三层

1. Controller 层定义了暴露给前端的接口。
2. Service 层定义了业务逻辑相关的代码。
3. Mapper 层定义了数据库相关的操作，由于使用了 mybatisplus 一些基础的增删改成都是集成自 BaseMapper 无需自己定义，简化了很多代码。

1. 前端请求发送 POST /system/group/create 请求，携带 GroupSaveReqVO 格式的 JSON 参数
2. Controller 层

@PostMapping("/create") // Spring MVC 匹配POST请求路由
@Operation(summary = "创建系统用户组")
@PreAuthorize("@ss.hasPermission('system:group:create')") // Spring Security 权限校验
public CommonResult<Long> createGroup(
    @Valid @RequestBody GroupSaveReqVO createReqVO // @Valid参数校验，@RequestBody解析请求体为VO
) {
    // 调用Service层处理业务，返回结果包装为统一响应格式
    return success(groupService.createGroup(createReqVO)); 
}

3. Service 层

@Override
public Long createGroup(GroupSaveReqVO createReqVO) {
    // 将前端传递的VO转换为数据库实体DO（匹配表结构）
    GroupDO group = BeanUtils.toBean(createReqVO, GroupDO.class);
    // 调用Mapper层插入数据到数据库
    groupMapper.insert(group);
    // 返回插入后的自增ID
    return group.getId();
}

4. Mapper 层

// 继承MyBatis-Plus的BaseMapper，获得通用CRUD方法
public interface BaseMapper <T> extends com.baomidou.mybatisplus.core.mapper.Mapper<T> {
    int insert(T entity); // MyBatis-Plus自动生成INSERT SQL，执行数据库插入
}

概念 VO、DTO、DO

在代码中经常涉及到这三者的定义和使用，有些项目使用不规范的话可能并不区分的这么细，但是我对于三者的关系和实际的使用场景简单罗列如下：

维度	ReqVO/RespVO（视图对象）	ReqDTO/RespDTO（数据传输对象）
核心定位	前端与控制层（Controller）的交互载体	服务层（或模块间）的数据传输契约
使用场景	前端提交请求参数、接收前端展示数据	服务间调用、模块内数据传递
字段设计	贴合前端页面需求（如表单字段、格式化数据）	贴合业务逻辑（如核心业务字段、校验规则）
变更驱动	前端页面需求变更（如新增输入框、展示列）	服务接口契约变更（如新增业务字段、逻辑）
数据来源	从 ReqDTO 转换而来（或直接接收前端参数）	从 DO（数据库实体）转换而来
典型示例	DeptPageReqVO（含分页 + 前端查询条件）DeptRespVO（含负责人姓名、格式化时间）	DeptSaveReqDTO（含部门名称、父部门 ID）DeptRespDTO（含部门 ID、名称、状态）

VO（View Object） ：聚焦前端视图交互，是控制层与前端的专属载体，字段设计贴合页面需求。

DTO（Data Transfer Object） ：聚焦服务间数据传输，是服务层的标准化契约，字段设计贴合业务逻辑

DO 是数据库表的代码镜像，是持久层与业务层的内部数据载体，仅负责数据存储映射，无业务逻辑。

维度	DO（数据对象）
核心定位	数据库表在代码中的实体映射
使用场景	数据访问层与业务层的内部数据载体
字段设计	与数据库表字段一一对应（含所有底层字段）
变更驱动	数据库表结构变更（如新增字段、修改类型）
数据来源	直接映射数据库表，由持久层操作生成
典型示例	GroupDO（映射system_group表，含 id、name、status 等字段）

前端 yudao-ui-admin-vue3

项目结构

• 业务模块：在 api 和 views 层均按 “系统、bpm、crm” 等业务域拆分子模块（如 system/group 同时管理接口与页面），让每个业务功能的代码链路高度集中，便于独立维护与迭代。
• 权限管控：通过 store/permission 和 store/user 深度联动，不仅支持动态路由的后端驱动生成，还能实现按钮级的权限校验，结合自定义指令完成细粒度操作控制，满足企业级后台的安全要求。
• 工程化分层：以 hooks 封装可复用业务逻辑、directives 封装通用交互行为，store 层通过 modules 区分业务与全局状态，既保证架构的扩展性，又让复杂后台的状态管理更有条理，特别适配多业务域的中大型后台系统开发。

yudao-ui-admin-vue3
├── src
│   ├── api                  # 接口封装层，按业务模块拆分，统一管理前后端接口交互
│   │   ├── system           # 系统管理模块接口
│   │   │   ├── group        # 用户组管理接口模块，封装用户组增删改查等接口
│   │   │   │   └── index.ts # 用户组管理接口实现
│   ├── assets               # 静态资源，存储图标、图片、全局样式等
│   ├── components           # 全局通用组件，可在各业务模块复用
│   ├── config/axios         # 请求封装与拦截器，配置请求全局规则、响应拦截逻辑
│   ├── directives           # 自定义指令，封装权限控制、拖拽、防抖等通用指令
│   ├── hooks                # 组合式 Hook，封装 web 交互、事件处理、业务逻辑复用等逻辑
│   ├── layout               # 框架布局，管理系统整体布局结构（侧边栏、顶部导航、标签页等）
│   ├── router               # 路由中心，管理静态路由和动态路由的注册、守卫逻辑
│   ├── store                # Pinia 模块，管理应用状态（核心模块如下）
│   │   ├── modules          # 业务模块状态（如 bpm、mall 等）
│   │   ├── permission.ts    # 权限状态（路由权限过滤、按钮权限校验，控制用户可访问页面和操作）
│   │   ├── user.ts          # 用户状态（用户信息、token、登录态管理，对接权限校验逻辑）
│   │   └── index.ts         # Pinia 模块注册入口
│   ├── styles               # 全局样式与 SCSS 变量，定义系统样式规范
│   ├── utils                # 工具函数，封装权限、字典、树结构、路由辅助等通用工具
│   └── views                # 业务页面，核心业务模块集合
│       ├── system           # 系统管理模块，包含各类系统配置与管理页面
│       │   ├── group        # 用户组管理业务页面模块
│       │   │   ├── index.vue # 用户组列表页，展示用户组数据、提供查询、操作入口
│       │   │   └── GroupForm.vue # 用户组表单页，实现用户组的新增、编辑功能
└── public                   # 公共静态资源，存储无需编译的静态文件

路由守卫核心流程解析

1. 身份验证：校验访问令牌存在性，已登录且目标为登录页时重定向至根路径。
2. 依赖初始化：按需拉取全局枚举字典、用户基础信息及权限菜单树，完成 Pinia 状态持久化与缓存写入。
3. 动态路由注入：依据后端菜单数据递归生成符合 Vue Router 规范的 RouteRecordRaw，通过 router.addRoute 在运行时注入路由表，并追加通配符 404 兜底。
4. 导航重置：利用 next({ path, query, replace: true }) 触发新一轮路由匹配，解决刷新后因 matcher 快照未更新导致的 404 问题，同时保留查询参数。

router.beforeEach(async (to, from, next) => {
  start()                 // 顶部进度条开始转
  loadStart()             // 页面 loading 蒙层

  if (getAccessToken()) { /* ===== ① 有 token ===== */
    if (to.path === '/login') {
      next({ path: '/' }) // 已登录再进登录页 → 直接踢走
      return
    }

    // 字典对应枚举
    const dictStore = useDictStoreWithOut()
    // 用户信息
    const userStore = useUserStoreWithOut()
    // 权限信息
    const permissionStore = usePermissionStoreWithOut()

    /* ③ 全局字典（性别、状态等下拉选项）只拉一次 */
    if (!dictStore.getIsSetDict) await dictStore.setDictMap()

    /* ④ 只要刷新页面 isSetUser 就是 false → 去拿用户数据 */
    if (!userStore.getIsSetUser) { // 是否设置过用户信息
      isRelogin.show = true                       // 显示“正在加载用户信息”遮罩
      await userStore.setUserInfoAction()         // 拿：用户详情 + 权限 + 菜单树
      isRelogin.show = false

      /* ⑤ 根据后端返回的菜单树 → 现拼前端路由 */
      await permissionStore.generateRoutes()      // 返回 addRouters[]
      permissionStore.getAddRouters.forEach(r =>  // 逐条塞进 vue-router
        router.addRoute(r as RouteRecordRaw))

      /* ⑥ 正确加载动态路由，必须使用 next(pathParams) 才能正确渲染新添加的路由  */
      const redirect = decodeURIComponent((from.query.redirect as string) || to.fullPath)
      const { paramsObject: query } = parseURL(redirect)
      next(to.path === redirect ? { ...to, replace: true } : { path: redirect, query })
    } else {
      next() // 用户、路由、字典都已就绪 → 直接放行
    }
  } else { /* ===== 无 token ===== */
    whiteList.includes(to.path)
      ? next()                           // 白名单页面直接过
      : next(`/login?redirect=${to.fullPath}`) // 其余统一跳登录
  }
})

“有 token → 拉用户 → 拼路由 → addRoute → 重跳带参 → 页面正常”

setUserInfoAction

setUserInfoAction 完成用户身份、权限、角色及菜单树的一次性拉取与持久化缓存，为后续路由生成、按钮级权限控制及全局用户信息渲染提供可复用的单一数据源。

export const useUserStore = defineStore('admin-user', {
  actions: {
    async setUserInfoAction() {
      /* 1. 如果连 token 都没有 → 直接 reset，后面代码不再执行 */
      if (!getAccessToken()) {
        this.resetState()
        return
      }

      /* 2. 先读本地缓存，保证刷新页面瞬间就能渲染，不会白屏 */
      let userInfo = wsCache.get(CACHE_KEY.USER)

      /* 3. 无论缓存是否存在，都去后端拉一次最新数据（失败也不踢人） */
      if (!userInfo) {
        userInfo = await getInfo()          // 第一次：必须等接口
      } else {
        try { userInfo = await getInfo() }  // 非第一次：后台悄悄更新
        catch {}
      }

      /* ===== 下面 4 行分别对应“4 件事” ===== */

      /* ① 拿权限标识集合 → 按钮级 v-hasPerm 会用它 */
      this.permissions = new Set(userInfo.permissions || [])

      /* ② 拿角色数组 → 按钮级 v-hasRole 会用它 */
      this.roles = userInfo.roles

      /* ③ 拿用户基本信息 → 顶部栏头像、个人中心等页面显示 */
      this.user = userInfo.user

      /* ④ 标记“我已经知道你是谁了”，路由守卫下次不再重复跑 */
      this.isSetUser = true

      /* ⑤ 把最新数据写缓存，下次刷新直接读，省一次接口 */
      wsCache.set(CACHE_KEY.USER, userInfo)

      /* ⑥ 把菜单树单独再写一份缓存 → permissionStore 会用它来拼装路由 */
      wsCache.set(CACHE_KEY.ROLE_ROUTERS, userInfo.menus)
    }
  }
})

generateRoutes

基于后端菜单树一次性生成可访问动态路由及侧边栏菜单数据。

export const usePermissionStore = defineStore('permission', {
  actions: {
    /**
     * usePermissionStore.generateRoutes()
     * 把【后端菜单】→【前端可访问路由】→【侧边栏菜单】
     * 一次性全算完，只在前端刷新后跑一遍。
     */
    async generateRoutes(): Promise<void> {
      return new Promise<void>(async (resolve) => {
        /* 1. 拿后端给的菜单树（登录时已缓存） */
        let res: AppCustomRouteRecordRaw[] = [];
        const roleRouters = wsCache.get(CACHE_KEY.ROLE_ROUTERS);
        if (roleRouters) res = roleRouters as AppCustomRouteRecordRaw[];
    
        /* 2. 递归把后端 JSON 转成 vue-router 需要的 RouteRecordRaw */
        const routerMap: AppRouteRecordRaw[] = generateRoute(res);
    
        /* 3. 追加“通配符 404”，保证任意非法路径都能落到 404 组件 */
        this.addRouters = routerMap.concat([
          {
            path: '/:path(.*)*',
            component: () => import('@/views/Error/404.vue'),
            name: '404Page',
            meta: { hidden: true, breadcrumb: false }
          }
        ]);
    
        /* 4. 拼出“完整菜单”：静态路由（login、404、dashboard）+ 动态路由
              用于侧边栏渲染、标签页、面包屑 */
        this.routers = cloneDeep(remainingRouter).concat(routerMap);
    
        /* 5. 通知外部“路已铺完”，可以 forEach(router.addRoute) 了 */
        resolve();
      });
    }
  }
}

拿到后端菜单相关数据，根据数据生成一份前端路由相关的配置。

动态加载路由

1. 将 permissionStore.getAddRouters 中的动态路由动态添加的路由注册表
2. 通过 next(routeParams) 重新渲染路由视图，否则动态路由不会正确被渲染

/* ④ 只要刷新页面 isSetUser 就是 false → 去拿用户数据 */
    if (!userStore.getIsSetUser) { // 是否设置过用户信息
      isRelogin.show = true                       // 显示“正在加载用户信息”遮罩
      await userStore.setUserInfoAction()         // 拿：用户详情 + 权限 + 菜单树
      isRelogin.show = false

      /* ⑤ 根据后端返回的菜单树 → 现拼前端路由 */
      await permissionStore.generateRoutes()      // 返回 addRouters[]
      permissionStore.getAddRouters.forEach(r =>  // 逐条塞进 vue-router
        router.addRoute(r as RouteRecordRaw)
      )

      /* ⑥ 正确加载动态路由，必须使用 next(pathParams) 才能正确渲染新添加的路由  */
      const redirect = decodeURIComponent((from.query.redirect as string) || to.fullPath)
      const { paramsObject: query } = parseURL(redirect)
      next(to.path === redirect ? { ...to, replace: true } : { path: redirect, query })
    } else {
      next() // 用户、路由、字典都已就绪 → 直接放行
    }

next() 使用分析

如果动态路由，直接使用 next() 未重新指定路由地址和参数。则无法匹配新添加的路由导致 404 。

使用 next({...to, replace: true }) 指定跳转动态路由的地址和参数。

结尾

就从“新增一个用户组”这道小入口出发，我把它当成芋道源码学习的第一课：后端以 Spring Boot 的调用链、权限模型；前端以 Vue3 的动态路由、表单校验与权限回显。如果你也在用芋道搭建自己的技术体系，欢迎持续关注，我们一起把这条主线走深、走实。

在Flutter应用开发中，图片选择是高频场景，无论是头像上传、相册选图还是拍照功能，都需要可靠的图片选择组件支撑。目前社区中最常用的两款组件分别是multi_image_picker_plus和官方

上周四下午，我正在调样式，突然电脑风扇开始咆哮。打开任务管理器：内存占用 15.5G / 16G。我人傻了，16G 内存开发个前端项目还能卡？仔细一看....

——从 toUTCString() 到 Intl.DateTimeFormat 的深度理解 时间与日期，是前端开发中最容易“踩坑”的部分。不同浏览器、不同区域、甚至不同系统语言，都会造成输出不一致。

你是不是经常遇到这样的场景？父组件的数据要传给子组件，子组件的事件要通知父组件，兄弟组件之间要共享状态...每次写Vue组件通信都觉得头大，不知道用哪种方式最合适？ 别担心！今天我就带你彻底搞懂Vue

图片 图片格式转换 webp -> jpg 等等 图片加边框水印 背景渐变 设备logo 去水印 图片编辑 视频 视频转gif （ffmpeg） gif 压缩 GIF 加文字（表情包） 视频压缩 视频

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

 

示例 1：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

 

提示：

• 1 <= strs.length <= 600
• 1 <= strs[i].length <= 100
• strs[i] 仅由 '0' 和 '1' 组成
• 1 <= m, n <= 100

前言

设 $\textit{strs}[i]$ 中 $0$ 的个数为 $\textit{cnt}_0[i]$，$1$ 的个数为 $\textit{cnt}_1[i]$，那么本题相当于：

• 有一个容量为 $(m,n)$ 的背包，至多可以装入 $m$ 个 $0$ 和 $n$ 个 $1$。现在有 $n$ 个物品，每个物品的体积为 $(\textit{cnt}_0[i],\textit{cnt}_1[i])$，表示该物品有 $\textit{cnt}_0[i]$ 个 $0$ 和 $\textit{cnt}_1[i]$ 个 $1$。问：最多可以选多少个物品？

这相当于背包有两种体积（二维），所以在定义状态的时候，相比只有一种体积的 0-1 背包，要多加一个参数。

如果你不了解 0-1 背包，请看【基础算法精讲 18】。

一、记忆化搜索

在一维 0-1 背包的基础上，多加一个参数，即定义 $\textit{dfs}(i,j,k)$ 表示在 $[0,i]$ 中选字符串，在 $0$ 的个数至多为 $j$，$1$ 的个数至多为 $k$ 的约束下，至多可以选多少个字符串。

考虑 $\textit{strs}[i]$ 选或不选：

• 不选：问题变成在 $[0,i-1]$ 中选字符串，在 $0$ 的个数至多为 $j$，$1$ 的个数至多为 $k$ 的约束下，至多可以选多少个字符串，即 $\textit{dfs}(i,j,k) = \textit{dfs}(i-1,j,k)$。
• 选：如果 $j\ge \textit{cnt}_0[i]$ 并且 $k\ge \textit{cnt}_1[i]$ 则可以选。问题变成在 $[0,i-1]$ 中选字符串，在 $0$ 的个数至多为 $j-\textit{cnt}_0[i]$，$1$ 的个数至多为 $k-\textit{cnt}_1[i]$ 的约束下，至多可以选多少个字符串，即 $\textit{dfs}(i,j,k) = \textit{dfs}(i-1,j-\textit{cnt}_0[i],k-\textit{cnt}_1[i]) + 1$。

两种情况取最大值，得

$$
\textit{dfs}(i,j,k) = \max(\textit{dfs}(i-1,j,k), \textit{dfs}(i-1,j-\textit{cnt}_0[i],k-\textit{cnt}_1[i]) + 1)
$$

如果

递归边界：$\textit{dfs}(-1,j,k)=0$。此时没有物品可以选。

递归入口：$\textit{dfs}(k-1,m,n)$，这是原问题，也是答案。其中 $k$ 为 $\textit{strs}$ 的长度。

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        cnt0 = [s.count('0') for s in strs]

        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
        def dfs(i: int, j: int, k: int) -> int:
            if i < 0:
                return 0
            res = dfs(i - 1, j, k)  # 不选 strs[i]
            cnt1 = len(strs[i]) - cnt0[i]
            if j >= cnt0[i] and k >= cnt1:
                res = max(res, dfs(i - 1, j - cnt0[i], k - cnt1) + 1)  # 选 strs[i]
            return res

        return dfs(len(strs) - 1, m, n)

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int k = strs.length;
        int[] cnt0 = new int[k];
        for (int i = 0; i < k; i++) {
            cnt0[i] = (int) strs[i].chars().filter(ch -> ch == '0').count();
        }

        int[][][] memo = new int[strs.length][m + 1][n + 1];
        for (int[][] mat : memo) {
            for (int[] arr : mat) {
                Arrays.fill(arr, -1); // -1 表示没有计算过
            }
        }
        return dfs(k - 1, m, n, strs, cnt0, memo);
    }

    private int dfs(int i, int j, int k, String[] strs, int[] cnt0, int[][][] memo) {
        if (i < 0) {
            return 0;
        }
        if (memo[i][j][k] != -1) { // 之前计算过
            return memo[i][j][k];
        }
        // 不选 strs[i]
        int res = dfs(i - 1, j, k, strs, cnt0, memo);  
        int cnt1 = strs[i].length() - cnt0[i];
        if (j >= cnt0[i] && k >= cnt1) {
            // 选 strs[i]
            res = Math.max(res, dfs(i - 1, j - cnt0[i], k - cnt1, strs, cnt0, memo) + 1);
        }
        return memo[i][j][k] = res; // 记忆化
    }
}

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<int> cnt0(strs.size());
        for (int i = 0; i < strs.size(); i++) {
            cnt0[i] = ranges::count(strs[i], '0');
        }

        vector memo(strs.size(), vector(m + 1, vector<int>(n + 1, -1))); // -1 表示没有计算过
        auto dfs = [&](this auto&& dfs, int i, int j, int k) -> int {
            if (i < 0) {
                return 0;
            }
            int& res = memo[i][j][k]; // 注意这里是引用
            if (res != -1) { // 之前计算过
                return res;
            }
            res = dfs(i - 1, j, k); // 不选 strs[i]
            int cnt1 = strs[i].size() - cnt0[i];
            if (j >= cnt0[i] && k >= cnt1) {
                res = max(res, dfs(i - 1, j - cnt0[i], k - cnt1) + 1); // 选 strs[i]
            }
            return res;
        };
        return dfs(strs.size() - 1, m, n);
    }
};

func findMaxForm(strs []string, m, n int) int {
    k := len(strs)
    cnt0 := make([]int, k)
    for i, s := range strs {
        cnt0[i] = strings.Count(s, "0")
    }

    memo := make([][][]int, k)
    for i := range memo {
        memo[i] = make([][]int, m+1)
        for j := range memo[i] {
            memo[i][j] = make([]int, n+1)
            for k := range memo[i][j] {
                memo[i][j][k] = -1 // -1 表示没有计算过
            }
        }
    }
    var dfs func(int, int, int) int
    dfs = func(i, j, k int) int {
        if i < 0 {
            return 0
        }
        p := &memo[i][j][k]
        if *p != -1 { // 之前计算过
            return *p
        }
        res := dfs(i-1, j, k) // 不选 strs[i]
        cnt1 := len(strs[i]) - cnt0[i]
        if j >= cnt0[i] && k >= cnt1 {
            res = max(res, dfs(i-1, j-cnt0[i], k-cnt1)+1) // 选 strs[i]
        }
        *p = res // 记忆化
        return res
    }
    return dfs(k-1, m, n)
}

复杂度分析

• 时间复杂度：$\mathcal{O}(kmn+L)$，其中 $k$ 为 $\textit{strs}$ 的长度，$L$ 为 $\textit{strs}$ 中所有字符串的长度之和。由于每个状态只会计算一次，动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题状态个数等于 $\mathcal{O}(kmn)$，单个状态的计算时间为 $\mathcal{O}(1)$，所以总的时间复杂度为 $\mathcal{O}(kmn)$。
• 空间复杂度：$\mathcal{O}(kmn)$。保存多少状态，就需要多少空间。

二、1:1 翻译成递推

我们可以去掉递归中的「递」，只保留「归」的部分，即自底向上计算。

具体来说，$f[i+1][j][k]$ 的定义和 $\textit{dfs}(i,j,k)$ 的定义是一样的，都表示在 $[0,i]$ 中选字符串，在 $0$ 的个数至多为 $j$，$1$ 的个数至多为 $k$ 的约束下，至多可以选多少个字符串。这里 $+1$ 是为了把 $\textit{dfs}(-1,j,k)$ 这个状态也翻译过来，这样我们可以把 $f[0][j][k]$ 作为初始值。

相应的递推式（状态转移方程）也和 $\textit{dfs}$ 一样：

$$
f[i+1][j][k] = \max(f[i][j][k], f[i][j-\textit{cnt}_0[i]][k-\textit{cnt}_1[i]] + 1)
$$

初始值 $f[0][j][k]=0$，翻译自递归边界 $\textit{dfs}(-1,j,k)=0$。

答案为 $f[k][m][n]$，翻译自递归入口 $\textit{dfs}(k-1,m,n)$。其中 $k$ 为 $\textit{strs}$ 的长度。

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        f = [[[0] * (n + 1) for _ in range(m + 1)] for _ in range(len(strs) + 1)]
        for i, s in enumerate(strs):
            cnt0 = s.count('0')
            cnt1 = len(s) - cnt0
            for j in range(m + 1):
                for k in range(n + 1):
                    if j >= cnt0 and k >= cnt1:
                        f[i + 1][j][k] = max(f[i][j][k], f[i][j - cnt0][k - cnt1] + 1)
                    else:
                        f[i + 1][j][k] = f[i][j][k]
        return f[-1][m][n]

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][][] f = new int[strs.length + 1][m + 1][n + 1];
        for (int i = 0; i < strs.length; i++) {
            int cnt0 = (int) strs[i].chars().filter(ch -> ch == '0').count();
            int cnt1 = strs[i].length() - cnt0;
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    if (j >= cnt0 && k >= cnt1) {
                        f[i + 1][j][k] = Math.max(f[i][j][k], f[i][j - cnt0][k - cnt1] + 1);
                    } else {
                        f[i + 1][j][k] = f[i][j][k];
                    }
                }
            }
        }
        return f[strs.length][m][n];
    }
}

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector f(strs.size() + 1, vector(m + 1, vector<int>(n + 1)));
        for (int i = 0; i < strs.size(); i++) {
            int cnt0 = ranges::count(strs[i], '0');
            int cnt1 = strs[i].size() - cnt0;
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    if (j >= cnt0 && k >= cnt1) {
                        f[i + 1][j][k] = max(f[i][j][k], f[i][j - cnt0][k - cnt1] + 1);
                    } else {
                        f[i + 1][j][k] = f[i][j][k];
                    }
                }
            }
        }
        return f.back()[m][n];
    }
};

func findMaxForm(strs []string, m, n int) int {
    k := len(strs)
    f := make([][][]int, k+1)
    for i := range f {
        f[i] = make([][]int, m+1)
        for j := range f[i] {
            f[i][j] = make([]int, n+1)
        }
    }
    for i, s := range strs {
        cnt0 := strings.Count(s, "0")
        cnt1 := len(s) - cnt0
        for j := range m + 1 {
            for k := range n + 1 {
                if j >= cnt0 && k >= cnt1 {
                    f[i+1][j][k] = max(f[i][j][k], f[i][j-cnt0][k-cnt1]+1)
                } else {
                    f[i+1][j][k] = f[i][j][k]
                }
            }
        }
    }
    return f[k][m][n]
}

复杂度分析

• 时间复杂度：$\mathcal{O}(kmn+L)$，其中 $k$ 为 $\textit{strs}$ 的长度，$L$ 为 $\textit{strs}$ 中所有字符串的长度之和。
• 空间复杂度：$\mathcal{O}(kmn)$。

三、空间优化

观察上面的状态转移方程，在计算 $f[i+1]$ 时，只会用到 $f[i]$，不会用到比 $i$ 更早的状态。

那么去掉第一个维度，把 $f[i+1]$ 和 $f[i]$ 保存到同一个二维数组中。

状态转移方程改为

$$
f[j][k] = \max(f[j][k], f[j-\textit{cnt}_0[i]][k-\textit{cnt}_1[i]] + 1)
$$

初始值 $f[j][k]=0$。

答案为 $f[m][n]$。

下面代码为什么要倒序循环，请看【基础算法精讲 18】。

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        f = [[0] * (n + 1) for _ in range(m + 1)]
        for s in strs:
            cnt0 = s.count('0')
            cnt1 = len(s) - cnt0
            for j in range(m, cnt0 - 1, -1):
                for k in range(n, cnt1 - 1, -1):
                    f[j][k] = max(f[j][k], f[j - cnt0][k - cnt1] + 1)
        return f[m][n]

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] f = new int[m + 1][n + 1];
        for (String s : strs) {
            int cnt0 = (int) s.chars().filter(ch -> ch == '0').count();
            int cnt1 = s.length() - cnt0;
            for (int j = m; j >= cnt0; j--) {
                for (int k = n; k >= cnt1; k--) {
                    f[j][k] = Math.max(f[j][k], f[j - cnt0][k - cnt1] + 1);
                }
            }
        }
        return f[m][n];
    }
}

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector f(m + 1, vector<int>(n + 1));
        for (string& s : strs) {
            int cnt0 = ranges::count(s, '0');
            int cnt1 = s.size() - cnt0;
            for (int j = m; j >= cnt0; j--) {
                for (int k = n; k >= cnt1; k--) {
                    f[j][k] = max(f[j][k], f[j - cnt0][k - cnt1] + 1);
                }
            }
        }
        return f[m][n];
    }
};

func findMaxForm(strs []string, m, n int) int {
    f := make([][]int, m+1)
    for i := range f {
        f[i] = make([]int, n+1)
    }
    for _, s := range strs {
        cnt0 := strings.Count(s, "0")
        cnt1 := len(s) - cnt0
        for j := m; j >= cnt0; j-- {
            for k := n; k >= cnt1; k-- {
                f[j][k] = max(f[j][k], f[j-cnt0][k-cnt1]+1)
            }
        }
    }
    return f[m][n]
}

进一步优化

比如 $n=m=90$，前 $3$ 个字符串总共有 $5$ 个 $0$ 和 $6$ 个 $1$，那么无论我们怎么选，也选不出几十个 $0$ 和 $1$，所以上面的代码中，其实有大量的循环是多余的。

为此，额外用两个变量 $\textit{sum}_0$ 和 $\textit{sum}_1$ 分别维护前 $i$ 个字符串中的 $0$ 的个数和 $1$ 的个数（但不能超过 $m$ 和 $n$）。循环的时候 $j$ 从 $\textit{sum}_0$ 开始，$k$ 从 $\textit{sum}_1$ 开始。

注意这个优化会导致只有一部分 $f[j][k]$ 被更新到，最大值并没有传递给 $f[m][n]$，可能留在二维数组中间的某个位置上。所以最后要遍历 $f$，取其中最大值作为答案。

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        f = [[0] * (n + 1) for _ in range(m + 1)]
        sum0 = sum1 = 0
        for s in strs:
            cnt0 = s.count('0')
            cnt1 = len(s) - cnt0
            sum0 = min(sum0 + cnt0, m)
            sum1 = min(sum1 + cnt1, n)
            for j in range(sum0, cnt0 - 1, -1):
                for k in range(sum1, cnt1 - 1, -1):
                    v = f[j - cnt0][k - cnt1] + 1
                    if v > f[j][k]:  # 手写 max，效率更高
                        f[j][k] = v
        return max(map(max, f))

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] f = new int[m + 1][n + 1];
        int sum0 = 0;
        int sum1 = 0;
        for (String s : strs) {
            int cnt0 = (int) s.chars().filter(ch -> ch == '0').count();
            int cnt1 = s.length() - cnt0;
            sum0 = Math.min(sum0 + cnt0, m);
            sum1 = Math.min(sum1 + cnt1, n);
            for (int j = sum0; j >= cnt0; j--) {
                for (int k = sum1; k >= cnt1; k--) {
                    f[j][k] = Math.max(f[j][k], f[j - cnt0][k - cnt1] + 1);
                }
            }
        }
        int ans = 0;
        for (int[] row : f) {
            for (int v : row) {
                ans = Math.max(ans, v);
            }
        }
        return ans;
    }
}

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector f(m + 1, vector<int>(n + 1));
        int sum0 = 0, sum1 = 0;
        for (string& s : strs) {
            int cnt0 = ranges::count(s, '0');
            int cnt1 = s.size() - cnt0;
            sum0 = min(sum0 + cnt0, m);
            sum1 = min(sum1 + cnt1, n);
            for (int j = sum0; j >= cnt0; j--) {
                for (int k = sum1; k >= cnt1; k--) {
                    f[j][k] = max(f[j][k], f[j - cnt0][k - cnt1] + 1);
                }
            }
        }
        int ans = 0;
        for (auto& row : f) {
            ans = max(ans, ranges::max(row));
        }
        return ans;
    }
};

func findMaxForm(strs []string, m, n int) (ans int) {
    f := make([][]int, m+1)
    for i := range f {
        f[i] = make([]int, n+1)
    }
    sum0, sum1 := 0, 0
    for _, s := range strs {
        cnt0 := strings.Count(s, "0")
        cnt1 := len(s) - cnt0
        sum0 = min(sum0+cnt0, m)
        sum1 = min(sum1+cnt1, n)
        for j := sum0; j >= cnt0; j-- {
            for k := sum1; k >= cnt1; k-- {
                f[j][k] = max(f[j][k], f[j-cnt0][k-cnt1]+1)
            }
        }
    }
    for _, row := range f {
        ans = max(ans, slices.Max(row))
    }
    return
}

复杂度分析

• 时间复杂度：$\mathcal{O}(kmn+L)$，其中 $k$ 为 $\textit{strs}$ 的长度，$L$ 为 $\textit{strs}$ 中所有字符串的长度之和。
• 空间复杂度：$\mathcal{O}(mn)$。

更多相似题目，见 动态规划题单 中的「§3.1 0-1 背包」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
7. 【本题相关】动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

（多维）01 背包

通常与「背包问题」相关的题考察的是 将原问题转换为「背包问题」的能力。

要将原问题转换为「背包问题」，往往需要从题目中抽象出「价值」与「成本」的概念。

这道题如果抽象成「背包问题」的话，应该是：

每个字符串的价值都是 1（对答案的贡献都是 1），选择的成本是该字符串中 1 的数量和 0 的数量。

问我们在 1 的数量不超过 $m$，0 的数量不超过 $n$ 的条件下，最大价值是多少。

由于每个字符串只能被选一次，且每个字符串的选与否对应了「价值」和「成本」，求解的问题也是「最大价值」是多少。

因此可以直接套用 01 背包的「状态定义」来做：

$f[k][i][j]$ 代表考虑前 k 件物品，在数字 1 容量不超过 $i$，数字 0 容量不超过 $j$ 的条件下的「最大价值」（每个字符串的价值均为 1）。

有了「状态定义」之后，「转移方程」也很好推导：

$$f[k][i][j] = \max(f[k - 1][i][j], f[k - 1][i - cnt[k][0]][j - cnt[k][1]] + 1)$$

其中 $cnt$ 数组记录的是字符串中出现的 $01$ 数量。

代码（为了方便理解，$P1$ 将第一件物品的处理单独抽了出来，也可以不抽出来，只需要将让物品下标从 $1$ 开始即可，见 $P2$）：

###Java

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        // 预处理每一个字符包含 0 和 1 的数量
        int[][] cnt = new int[len][2];
        for (int i = 0; i < len; i++) {
            String str = strs[i];
            int zero = 0, one = 0;
            for (char c : str.toCharArray()) {
                if (c == '0') {
                    zero++;
                } else {
                    one++;
                }
            }
            cnt[i] = new int[]{zero, one}; 
        }

        // 处理只考虑第一件物品的情况
        int[][][] f = new int[len][m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                f[0][i][j] = (i >= cnt[0][0] && j >= cnt[0][1]) ? 1 : 0;
            }
        }

        // 处理考虑其余物品的情况
        for (int k = 1; k < len; k++) {
            int zero = cnt[k][0], one = cnt[k][1];
            for (int i = 0; i <= m; i++) {
                for (int j = 0; j <= n; j++) {
                    // 不选择第 k 件物品
                    int a = f[k-1][i][j];
                    // 选择第 k 件物品（前提是有足够的 m 和 n 额度可使用）
                    int b = (i >= zero && j >= one) ? f[k-1][i-zero][j-one] + 1 : 0;
                    f[k][i][j] = Math.max(a, b);
                }
            }
        }
        return f[len-1][m][n];
    }
}

###Java

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][] cnt = new int[len][2];
        for (int i = 0; i < len; i++) {
            String str = strs[i];
            int zero = 0, one = 0;
            for (char c : str.toCharArray()) {
                if (c == '0') zero++;    
                else one++;

            }
            cnt[i] = new int[]{zero, one}; 
        }
        int[][][] f = new int[len + 1][m + 1][n + 1];
        for (int k = 1; k <= len; k++) {
            int zero = cnt[k - 1][0], one = cnt[k - 1][1];
            for (int i = 0; i <= m; i++) {
                for (int j = 0; j <= n; j++) {
                    int a = f[k - 1][i][j];
                    int b = (i >= zero && j >= one) ? f[k - 1][i - zero][j - one] + 1 : 0;
                    f[k][i][j] = Math.max(a, b);
                }
            }
        }
        return f[len][m][n];
    }
}

• 时间复杂度：预处理字符串的复杂度为 $O(\sum_{i = 0}^{k - 1}len(strs[i]))$，处理状态转移的 $O(k * m * n)$。整体复杂度为：$O(k * m * n + \sum_{i = 0}^{k - 1}len(strs[i]))$
• 空间复杂度：$O(k * m * n)$

---

滚动数组

根据「状态转移」可知，更新某个物品的状态时，只依赖于上一个物品的状态。

因此，可以使用「滚动数组」的方式进行空间优化。

代码（为了方便理解，$P1$ 将第一件物品的处理单独抽了出来，也可以不抽出来，只需要将让物品下标从 $1$ 开始即可，见 $P2$）：

###Java

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        // 预处理每一个字符包含 0 和 1 的数量
        int[][] cnt = new int[len][2];
        for (int i = 0; i < len; i++) {
            String str = strs[i];
            int zero = 0, one = 0;
            for (char c : str.toCharArray()) {
                if (c == '0') {
                    zero++;
                } else {
                    one++;
                }
            }
            cnt[i] = new int[]{zero, one}; 
        }

        // 处理只考虑第一件物品的情况
        // 「物品维度」修改为 2 
        int[][][] f = new int[2][m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                f[0][i][j] = (i >= cnt[0][0] && j >= cnt[0][1]) ? 1 : 0;
            }
        }

        // 处理考虑其余物品的情况
        for (int k = 1; k < len; k++) {
            int zero = cnt[k][0], one = cnt[k][1];
            for (int i = 0; i <= m; i++) {
                for (int j = 0; j <= n; j++) {
                    // 不选择第 k 件物品
                    // 将 k-1 修改为 (k-1)&1
                    int a = f[(k-1)&1][i][j];
                    // 选择第 k 件物品（前提是有足够的 m 和 n 额度可使用）
                    // 将 k-1 修改为 (k-1)&1
                    int b = (i >= zero && j >= one) ? f[(k-1)&1][i-zero][j-one] + 1 : 0;
                    f[k&1][i][j] = Math.max(a, b);
                }
            }
        }
        // 将 len-1 修改为 (len-1)&1
        return f[(len-1)&1][m][n];
    }
}

###Java

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][] cnt = new int[len][2];
        for (int i = 0; i < len; i++) {
            String str = strs[i];
            int zero = 0, one = 0;
            for (char c : str.toCharArray()) {
                if (c == '0') zero++;
                else one++; 
            }
            cnt[i] = new int[]{zero, one}; 
        }
        int[][][] f = new int[2][m + 1][n + 1];
        for (int k = 1; k <= len; k++) {
            int zero = cnt[k - 1][0], one = cnt[k - 1][1];
            for (int i = 0; i <= m; i++) {
                for (int j = 0; j <= n; j++) {
                    int a = f[(k-1) & 1][i][j];
                    int b = (i >= zero && j >= one) ? f[(k-1) & 1][i - zero][j - one] + 1 : 0;
                    f[k&1][i][j] = Math.max(a, b);
                }
            }
        }
        return f[len&1][m][n];
    }
}

• 时间复杂度：预处理字符串的复杂度为 $O(\sum_{i = 0}^{k - 1}len(strs[i]))$，处理状态转移的 $O(k * m * n)$。整体复杂度为：$O(k * m * n + \sum_{i = 0}^{k - 1}len(strs[i]))$
• 空间复杂度：$O(m * n)$

---

一维空间优化

事实上，我们还能继续进行空间优化。

再次观察我们的「状态转移方程」发现：$f[k][i][j]$ 不仅仅依赖于上一行，还明确依赖于比 $i$ 小和比 $j$ 小的状态。

即可只依赖于「上一行」中「正上方」的格子，和「正上方左边」的格子。

对应到「朴素的 01 背包问题」依赖关系如图：

因此可直接参考「01 背包的空间优化」方式：取消掉「物品维度」，然后调整容量的遍历顺序。

代码：

###Java

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][] cnt = new int[len][2];
        for (int i = 0; i < len; i++) {
            int zero = 0, one = 0;
            for (char c : strs[i].toCharArray()) {
                if (c == '0') zero++;
                else one++;
            }
            cnt[i] = new int[]{zero, one};
        }
        int[][] f = new int[m + 1][n + 1];
        for (int k = 0; k < len; k++) {
            int zero = cnt[k][0], one = cnt[k][1];
            for (int i = m; i >= zero; i--) {
                for (int j = n; j >= one; j--) {
                    f[i][j] = Math.max(f[i][j], f[i - zero][j - one] + 1);
                }
            }
        }
        return f[m][n];
    }
}

• 时间复杂度：预处理字符串的复杂度为 $O(\sum_{i = 0}^{k - 1}len(strs[i]))$，处理状态转移的 $O(k * m * n)$。整体复杂度为：$O(k * m * n + \sum_{i = 0}^{k - 1}len(strs[i]))$
• 空间复杂度：$O(m * n)$

---

其他「背包」问题

看不懂「背包」解决方案？

以下是公主号讲过的「背包专题」系列目录，欢迎 关注 🍭🍭🍭 ：

1. 01背包 : 背包问题 第一讲

   1. 【练习】01背包 : 背包问题 第二讲

   2. 【学习&练习】01背包 : 背包问题 第三讲

   3. 【加餐/补充】01 背包：背包问题 第二十一讲

2. 完全背包 : 背包问题 第四讲

   1. 【练习】完全背包 : 背包问题 第五讲

   2. 【练习】完全背包 : 背包问题 第六讲

   3. 【练习】完全背包 : 背包问题 第七讲

3. 多重背包 : 背包问题 第八讲

4. 多重背包（优化篇）

   1. 【上】多重背包（优化篇）: 背包问题 第九讲

   2. 【下】多重背包（优化篇）: 背包问题 第十讲

5. 混合背包 : 背包问题 第十一讲

6. 分组背包 : 背包问题 第十二讲

   1. 【练习】分组背包 : 背包问题 第十三讲

7. 多维背包

   1. 【练习】多维背包 : 背包问题 第十四讲

   2. 【练习】多维背包 : 背包问题 第十五讲

8. 树形背包 : 背包问题 第十六讲

   1. 【练习篇】树形背包 : 背包问题 第十七讲

   2. 【练习篇】树形背包 : 背包问题 第十八讲

9. 背包求方案数

   1. 【练习】背包求方案数 : 背包问题 第十九讲

   2. 【练习】背包求方案数 : 背包问题 第十五讲

   [注：因为之前实在找不到题，这道「求方案数」题作为“特殊”的「多维费用背包问题求方案数」讲过]

10. 背包求具体方案

    1. 【练习】背包求具体方案 : 背包问题 第二十讲

11. 泛化背包

    1. 【练习】泛化背包

---

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/

也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

思路：把总共的 0 和 1 的个数视为背包的容量，每一个字符串视为装进背包的物品。这道题就可以使用 0-1 背包问题的思路完成，这里的目标值是能放进背包的字符串的数量。

---

动态规划的思路是：物品一个一个尝试，容量一点一点尝试，每个物品分类讨论的标准是：选与不选。

定义状态：尝试题目问啥，就把啥定义成状态。dp[i][j][k] 表示输入字符串在子区间 [0, i] 能够使用 j 个 0 和 k 个 1 的字符串的最大数量。
状态转移方程：
$$dp[i][j][k]=
\begin{cases}
dp[i - 1][j][k], & 不选择当前考虑的字符串，至少是这个数值\
dp[i - 1][j - 当前字符串使用 ;0; 的个数][k - 当前字符串使用 ;1; 的个数] + 1 & 选择当前考虑的字符串
\end{cases}
$$
初始化：为了避免分类讨论，通常多设置一行。这里可以认为，第 $0$ 个字符串是空串。第 $0$ 行默认初始化为 $0$。
输出：输出是最后一个状态，即：dp[len][m][n]。

参考代码1：

###Java

public class Solution {

    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][][] dp = new int[len + 1][m + 1][n + 1];

        for (int i = 1; i <= len; i++) {
            // 注意：有一位偏移
            int[] count = countZeroAndOne(strs[i - 1]);
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    // 先把上一行抄下来
                    dp[i][j][k] = dp[i - 1][j][k];
                    int zeros = count[0];
                    int ones = count[1];
                    if (j >= zeros && k >= ones) {
                        dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - zeros][k - ones] + 1);
                    }
                }
            }
        }
        return dp[len][m][n];
    }

    private int[] countZeroAndOne(String str) {
        int[] cnt = new int[2];
        for (char c : str.toCharArray()) {
            cnt[c - '0']++;
        }
        return cnt;
    }
}

第 5 步：思考优化空间

因为当前行只参考了上一行的值，因此可以使用「滚动数组」，也可以「从后向前赋值」。

参考代码2：这里选用「从后向前赋值」

###Java

public class Solution {

    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        dp[0][0] = 0;
        for (String s : strs) {
            int[] zeroAndOne = calcZeroAndOne(s);
            int zeros = zeroAndOne[0];
            int ones = zeroAndOne[1];
            for (int i = m; i >= zeros; i--) {
                for (int j = n; j >= ones; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
                }
            }
        }
        return dp[m][n];
    }

    private int[] calcZeroAndOne(String str) {
        int[] res = new int[2];
        for (char c : str.toCharArray()) {
            res[c - '0']++;
        }
        return res;
    }
}

前言 大家好，我是奈德丽。 周末闲着没事，突然想研究一下 create-vite 是怎么实现的。打开源码一看，我人都傻了——核心逻辑就几百行代码！这让我突然来了兴致：既然这么简单，为什么不自己撸一个呢

Kotlin泛型位置规律与设计考量 1. 泛型出现的位置分类 在Kotlin中，泛型可以出现在以下几个主要位置： 1.1 类声明中的泛型 规律： 泛型参数

1. 前言 初学 JavaScript 的时候，经常会遇到一些令人困惑的现象，比如： 为什么一个值会不等于它自己呢？ 今天，我们就来深入探究这个问题。 2. NaN 的本质：一个特殊的“数字” NaN

从匿名递归开始 先看一段看似难以理解的代码： 执行结果是： 即 6!(6 的阶乘（factorial of 6）)。 在数学中，**阶乘（factorial）**是指一个正整数与它所有比它小的正整数的

本文介绍setTimeout和setInterval的执行误差原因，分析setInterval的任务堆叠、误差累积和内存泄漏问题，提出使用递归setTimeout封装的安全方案。

🌟 引言 在日常 SPA 开发中，你是否遇到过这些困扰： 内容更新却不改变 URL，刷新或分享后无法到达当前视图 用户点击后退/前进导致状态丢失，体验不一致 页面刷新后无法恢复视图与数据，需重新操作

nativeRef与ViewRef、AbstractBaseView、Pager以及ViewContainer的关系分析 本文将深入分析KuiklyUI框架中nativeRef与ViewRef、Abs

重构老项目的时候，看到代码里到处都是这样的判断： 字符串满天飞，每次都要小心翼翼地打字，生怕打错一个字母。想用枚举来管理这些常量，但 JavaScript 又没有原生的 enum 关键字。 网上搜了一

前言 Word 转 HTML 工具 使用 mammoth 将 Word 文档转换为 HTML，特别适用于协议文档的在线预览。 安装依赖 bash 完整代码 javascript 目录结构 text 在