RustInPractice（27）：动态规划与系列回顾
动态规划把重叠子问题保存为状态表：先定义状态，再写转移，再决定初始化和遍历顺序。它也是 RustInPractice 主线的收官篇。
对应
dynamic_programming。TUI 番外将另行发布。
Fibonacci 只保留前两个状态，将空间从 O(n) 降至 O(1)。0/1 背包一维表必须逆序遍历容量，防止同一物品被重复选择。LCS demo 按 UTF-8 bytes 计算，非 ASCII 的“字符级 LCS”需要不同表示。
当前背包 demo 假设容量非负、weights/values 等长且权重有效；真实 API 应先验证这些输入，避免负数转 usize 或数组越界。
主线至此完成：基础与 Cargo，所有权类型系统，工程并发，最后落到服务、存储和算法。下一步可以继续 TUI 番外，或以一个带测试、配置、数据库和 HTTP 的 capstone 收束实践。
RustInPractice 主线第 27 篇完结。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 WALL-E's Blog！
相关推荐
2026-07-06
现代 C++ 实战（23）：字符串搜索与动态规划
第 22 篇 的图算法处理「关系」；本篇进入算法面试的两大支柱：字符串搜索（在文本中找模式）和动态规划（把大问题拆成重叠子问题）。KMP 和 Boyer-Moore 解决搜索，背包和 LCS 解决 DP——掌握这些，LeetCode 中等题大半有思路。 demo：ref/cpp_demo/algorithms/string_search/ + ref/cpp_demo/algorithms/dynamic_programming/。 这是「现代 C++ 实战」系列的第 23 篇。建议先读 第 22 篇：图算法。 一、字符串搜索全景在文本 text（长度 n）中查找模式 pattern（长度 m）： 算法 时间 思路 适用 暴力 O(nm) 每个位置逐字符比 短模式、教学 KMP O(n+m) 前缀函数，失配不回退 text 通用、面试必考 Boyer-Moore 最好 O(n/m) 从右向左，坏字符跳跃 长模式、实际文本搜索 Rabin-Karp 平均 O(n+m) 滚动哈希，先比哈希再验证 多模式匹配 1234text: A ...
2026-07-23
RustInPractice（26）：排序与字符串搜索
排序 demo 用 &mut [i32] 直接操作切片，搜索 demo 用字节序列实现朴素匹配与 KMP。它们适合理解复杂度，生产代码仍应优先标准库。 对应 sorting、string_search。下一篇：动态规划与系列收官。 冒泡和插入排序是 O(n²)，快速排序平均 O(n log n)，但最后元素 pivot 对已排序输入会退化并导致深递归。默认应使用 sort_unstable()，除非需要稳定排序。 KMP 的 LPS 表让失配后不必回退 haystack，因此复杂度为 O(m+n)。当前实现按 UTF-8 字节搜索，返回字节偏移；非 ASCII 文本不能把该值当字符索引或随意切片。 测试必须覆盖空 slice、单元素、重复值、空 pattern 和 Unicode 边界。 下一篇：动态规划与 RustInPractice 主线回顾。
2026-07-20
RustInPractice（04）：数组、Vec、元组与迭代器
集合是所有权规则最容易“看得见”的地方：同样是遍历，for item in values、for item in &values、for item in &mut values 的语义完全不同。本篇借 array_demo、tuple_demo 和 closure_demo 建立容器与迭代的基本选择。 这是 RustInPractice 的第 04 篇。对应 demo：array_demo、tuple_demo、closure_demo。下一篇用 Option、Result 和 ? 处理可恢复错误。 一、固定数组和动态 Vec[T; N] 的长度是类型的一部分，适合编译期已知数量的数据： 1let weekdays: [&str; 3] = ["Mon", "Tue", "Wed"]; Vec<T> 是可增长的连续容器，适合运行时才能知道长度的数据： 1234let mut scores = vec![80, 92, 76];scores.push(88);scores.re...
2026-07-22
RustInPractice（21）：CLI、配置、日志与错误边界
语言特性最终要落到程序入口。一个可靠 CLI 应将参数解析、配置读取、业务逻辑、日志和错误呈现分层，使核心代码可测试、命令行只是薄薄的一层适配器。 RustInPractice 第三季收官篇。对应 demo：learning_guide、argv_demo、filesystem_demo。第四季将进入 Axum、WebSocket、SQLite 与算法实践。 一、用 Clap 声明命令结构12345#[derive(clap::Subcommand)]enum Commands { List, Demo { name: String },} learning_guide 将 subcommand 解析后交给 demos::run。入口只负责输入适配，模块负责业务行为，这让同一逻辑既能被 CLI 调用，也能被测试直接调用。 二、配置来源要有优先级常见顺序是：命令行参数 > 环境变量 > 配置文件 > 安全默认值。不要把密钥写进默认值、示例输出或日志；示例使用 user@example.com、<T...
2026-07-24
RustInPractice TUI（02）：模态表单与 UI 状态
表单的难点不是画两个输入框，而是让输入状态在控件和提交逻辑之间保持一致。dialog_form 用模态 Dialog 暂时接管事件循环，并用共享数据保存输入。 对应 turbo-vision/dialog_form。截图中的姓名和邮箱均为 demo 固定示例数据。 状态归属InputLine 接收 Rc<RefCell<String>>。Rc 允许输入框和提交代码共同持有同一份字符串，RefCell 把借用检查放到运行时。这个组合只适合单线程 UI 状态；跨线程更新应使用消息通道或同步原语。 12345678let name_data = Rc::new(RefCell::new(String::from("Alice")));dialog.add(Box::new( InputLineBuilder::new() .bounds(Rect::new(14, 3, 44, 3)) .max_length(28) .data(Rc::clone(&name_data)) ...
2026-07-21
RustInPractice（08）：所有权、Move、Copy 与 Clone
Rust 的所有权不是“手动管理内存”的另一种说法，而是一套资源责任规则：一个值在任意时刻只有一个拥有者；拥有者离开作用域时，值会被自动清理；赋值和传参默认会转移所有权。 这是 RustInPractice 第二季的第 08 篇。对应 demo：ownership/move_demo。下一篇讲借用：不转移所有权，如何安全地访问一个值。 一、Move：责任转移，不是字节复制1234let first = String::from("hello");let second = first;// println!("{first}"); // 编译错误：first 已被移动println!("{second}"); String 管理一段堆内存。若赋值后两个变量都可用，它们可能在作用域结束时重复释放同一块资源。Rust 因而将赋值定义为 move：second 接管资源，first 失效。 这条规则也适用于函数： 123456fn consume(text: String) &#...
