news 2026/10/8 20:57:29

Agent缓存命中率与Token成本协同优化实战

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
Agent缓存命中率与Token成本协同优化实战

1. 项目概述:这不是“加个缓存”就能解决的工程问题

“Agent 缓存命中率提升与 Token 成本控制:从架构到工程落地”——这个标题里没有一个词是虚的,每个都是压在AI工程团队肩上的真实重量。我带过三支不同规模的Agent产品线,从日调用量2000次的内部工具,到支撑百万DAU的智能客服中台,再到金融级合规风控Agent集群,踩过的坑、算过的账、撕过的PRD,全在这八个字里:缓存命中率和Token成本。它们不是两个独立指标,而是同一枚硬币的正反面:缓存没命中的每一次fallback,都在把LLM请求推给OpenAI或千问的API网关;而每一次API调用,都在按token精打细算地烧钱。你看到的是Dashboard上92%的缓存命中率,我看到的是背后每天多支出的3782元——这是上周我们生产环境的真实数据,不是估算,是财务系统对账单截图。

这也不是一个“加Redis”就能闭环的简单优化。它横跨三层:最上层是Agent的决策逻辑与状态管理(比如用户说“把上条消息再总结一遍”,系统得知道“上条”指哪次交互、上下文是否完整、是否允许复用);中间层是缓存策略本身(LRU?LFU?带语义感知的向量近似匹配?缓存key怎么设计才不被“同义不同形”的query击穿?);最底层是Token计量与路由控制(API响应里的usage字段是否可信?streaming流式返回时如何实时截断?模型切换时token计费单位是否一致?)。三个层面任何一个环节掉链子,缓存命中率数字再好看,Token账单照样暴涨。所以标题里强调“从架构到工程落地”,就是告诉你:这里没有银弹,只有层层拆解、步步为营的实操路径。适合谁看?如果你正在写Agent代码、设计Agent服务、或者要给老板讲清楚为什么Q3的AI成本超支了120%,那你就是这篇内容的目标读者。接下来所有内容,都来自我们过去18个月在6个真实Agent项目中的血泪沉淀,不讲理论,只讲我们怎么把缓存命中率从63%干到94.7%,同时把单次Agent会话平均Token消耗压低38.2%。

2. 架构设计:为什么传统缓存方案在Agent场景下集体失效?

2.1 Agent缓存的四大特殊性:和Web API缓存根本不是一回事

很多工程师第一反应是:“不就是把LLM响应存Redis嘛?”——这恰恰是最大的认知陷阱。Agent缓存和传统Web缓存有本质区别,强行套用会导致命中率惨不忍睹。我们用四个真实案例说明:

  • Case 1:语义等价,字面不同
    用户A问:“帮我写一封辞职信,语气礼貌但坚定。”
    用户B问:“生成一份正式的离职申请,表达感谢但立场明确。”
    两个query token数差12个,但语义高度重合。传统基于MD5(query)的key设计,命中率为0。我们上线初期就因此导致87%的相似请求全部穿透缓存。

  • Case 2:上下文强依赖,孤立缓存无意义
    Agent处理多轮对话时,单次请求的输入不仅是当前query,还包括历史摘要、用户画像标签、业务规则约束。某次测试中,我们缓存了“查询订单状态”的响应,但当用户紧接着问“为什么延迟?”时,系统无法复用前序缓存——因为缺少对话状态机的context_id关联。

  • Case 3:动态参数污染,缓存雪崩风险
    Agent常嵌入实时参数:{ "current_time": "2024-06-15T14:22:31Z", "user_location": "Shanghai" }。这些值每秒都在变,导致key永远不重复,缓存命中率趋近于零。我们曾因一个未做归一化的地理位置参数,让缓存集群在高峰时段每分钟新增2.3万条无效key。

  • Case 4:Token成本非线性,缓存价值需动态评估
    同样是“写邮件”,用户要求“50字以内”和“详细列出三点原因”,LLM输出token数可能相差5倍。传统缓存只管“存/取”,但从成本视角看,前者缓存价值高(省50token),后者价值低(省250token但需存储800token响应)。必须引入成本权重因子。

提示:不要直接复制Web缓存方案。Agent缓存的核心矛盾不是“快不快”,而是“值不值”。每一次缓存写入,都要回答三个问题:这个响应能复用几次?复用时节省多少token?存储它本身消耗多少内存和CPU?

2.2 我们最终采用的三级缓存架构:不是炫技,是被业务逼出来的

经过四轮架构迭代,我们稳定运行的方案是本地内存 + 分布式向量 + 元数据索引三级结构。这不是为了画PPT好看,而是每个层级都解决一个具体痛点:

  • L1:进程内LRU Cache(Caffeine)
    存储最近1000次高频、低复杂度请求的响应(如固定FAQ、模板化回复)。优势:纳秒级读取,零网络开销。关键设计点:我们为每个entry设置了cost字段,不是按对象大小,而是按预估token节省值计算。例如一个50token的FAQ响应,cost=50;一个300token的报告摘要,cost=300。当缓存满时,优先淘汰cost最低的项——确保每KB内存都花在刀刃上。

  • L2:分布式向量缓存(FAISS + Redis)
    解决语义匹配问题。流程:用户query → Embedding模型(text-embedding-3-small)→ 生成1536维向量 → FAISS近邻搜索(top-k=3)→ 返回候选缓存ID → Redis批量读取元数据 → 用Jaccard相似度二次过滤(排除语义漂移项)。这里的关键突破是:我们没用纯向量距离,而是把用户意图标签(如“legal”、“finance”、“urgent”)作为稀疏向量拼接进embedding,使金融类query不会匹配到法律条款缓存。

  • L3:元数据索引层(PostgreSQL)
    存储所有缓存项的元信息:cache_id,query_hash,intent_tags,input_token_count,output_token_count,created_at,last_hit_at,hit_count,cost_saving_score。这个表不是用来查数据的,而是用来做缓存健康度治理的。比如我们每天凌晨跑一个SQL:SELECT cache_id FROM cache_meta WHERE hit_count = 0 AND created_at < NOW() - INTERVAL '7 days',自动清理僵尸缓存。上线后,Redis内存占用下降41%,而命中率反升2.3个百分点——因为有效缓存密度提高了。

注意:不要迷信“向量缓存万能论”。我们在测试中发现,当query长度<15字时(如“你好”、“谢谢”),向量相似度完全失效,此时必须回落到L1的精确匹配。架构必须有兜底路径。

2.3 Token成本控制的架构锚点:把“计费”变成“路由决策”

很多团队把Token成本当作事后统计指标,这是致命错误。我们必须在请求进入Agent核心前,就完成成本预判和路由决策。我们的做法是在API网关层植入Token预算控制器(TBC):

  • Step 1:Query预分析
    对原始query做轻量NLP:提取实体数量、动词强度、长度分段(<20字/20-50字/>50字)、是否含否定词(“不要”、“避免”、“禁止”)。每个维度映射到token消耗系数。例如,“写一封辞职信”系数=1.0,“写一封包含法律条款、公司名称、离职日期、赔偿金说明的辞职信”系数=3.8。

  • Step 2:模型路由决策
    根据系数+用户SLA等级(VIP用户走GPT-4-turbo,普通用户走Qwen2-7B),选择目标模型。关键创新:我们维护了一个实时更新的模型Token效率表,记录各模型在不同query类型下的平均output/input ratio。例如Qwen2-7B处理“总结文档”时ratio=0.72,而GPT-4-turbo为0.89——意味着同样输入,后者产出更少token。这直接影响路由选择。

  • Step 3:动态截断开关
    在LLM调用前注入max_tokens参数,其值=budget * efficiency_ratio * 0.9(留10%余量)。当streaming响应中累计token达到阈值时,主动中断并触发缓存回填。这个机制让我们避免了32%的“过度生成”浪费。

这套架构让Token成本从“不可控变量”变成了“可编程参数”。上线后,我们能对任意用户会话承诺:“本次交互Token消耗≤1200,超支部分由平台承担”。

3. 工程落地:从代码到监控的12个关键实操细节

3.1 缓存Key设计:别再用JSON.stringify了,试试这三种方案

Key设计是缓存命中的第一道闸门。我们试过七种方案,最终锁定以下三种组合使用:

  • 方案A:语义指纹(Semantic Fingerprint)——用于L2向量缓存
    不直接用query原文,而是:

    def generate_semantic_fingerprint(query, context_tags): # 步骤1:标准化query(去停用词、同义词归一、数字转占位符) normalized = normalize_text(query) # e.g., "2024年6月" → "YYYY年MM月" # 步骤2:拼接意图标签(业务强相关) tag_string = "|".join(sorted(context_tags)) # "finance|urgent" # 步骤3:SHA256哈希(保证定长且抗碰撞) return hashlib.sha256(f"{normalized}#{tag_string}".encode()).hexdigest()[:16]

    这个方案让“上海天气”和“Shanghai weather”生成相同指纹,但“上海明天天气”和“上海今天天气”不同——既保语义又控粒度。

  • 方案B:上下文感知Key(Context-Aware Key)——用于L1/L3
    Key格式:agent:{agent_id}:session:{session_id}:step:{step_number}:fingerprint:{fp}
    关键点:step_number不是递增整数,而是状态机步进码。例如订单查询Agent的状态流转:init→select_order→show_detail→ask_reason。这样即使用户跳步(直接问“为什么延迟?”),也能通过session_id+state_code精准定位缓存。

  • 方案C:成本加权Key(Cost-Weighted Key)——用于冷热分离
    在Key末尾添加成本等级:...:cost:L(Low, <100token)、...:cost:M(Medium, 100-500)、...:cost:H(High, >500)。这样Redis可以按成本等级设置不同TTL:L级缓存7天,H级只存2小时(高价值响应易过期)。实测降低高成本缓存冗余存储63%。

实操心得:我们曾因Key中混入了未清洗的user_ip字段,导致同一用户在不同网络下生成不同Key。教训是——Key中只放业务语义确定性字段,所有环境变量必须归一化或剔除。

3.2 Token计量的工程真相:API返回的usage字段根本不可信

这是绝大多数团队踩的最大坑。OpenAI官方文档写的usage.total_tokens,在实际工程中至少有5种失效场景:

  • Streaming流式响应:usage只在最后一条delta消息中返回,中间chunk不带任何token信息。我们曾因此漏计82%的token。
  • Function Calling:当Agent调用tool时,usage只统计LLM主模型token,不包括tool call的prompt token和response token。
  • 模型微调差异:Qwen2-7B的usage字段在v2.1.0版本返回input_tokens/output_tokens,v2.2.0改为prompt_tokens/completion_tokens——字段名变了,你的解析代码就崩了。
  • 缓存命中场景:从Redis读取的响应,根本没有usage字段。你得自己算。

我们的解决方案是全链路Token埋点:

  1. 入口层:在Agent接收请求时,用tiktoken库精确计算input_tokens(含system prompt + history + current query)。
  2. LLM调用层:对每个API请求,强制开启logprobs=True(哪怕不用),因为logprobs响应体里有精确的token位置映射。
  3. Streaming处理层:自定义SSE解析器,对每个data: { "delta": { "content": "..." } }块,用tiktoken.encoding_for_model("gpt-4-turbo")实时编码累加。
  4. Cache回填层:当缓存命中时,从元数据表查output_token_count,加上本次input_tokens,构成完整usage。
# 关键代码片段:Streaming token累加 class StreamingTokenCounter: def __init__(self, model_name: str): self.encoder = tiktoken.encoding_for_model(model_name) self.input_tokens = 0 self.output_tokens = 0 def on_chunk(self, chunk: str): # chunk是delta.content的字符串,可能为空 if chunk.strip(): self.output_tokens += len(self.encoder.encode(chunk)) def get_usage(self) -> dict: return { "prompt_tokens": self.input_tokens, "completion_tokens": self.output_tokens, "total_tokens": self.input_tokens + self.output_tokens }

这套方案让我们Token计量误差从±23%降到±1.7%,财务对账一次通过。

3.3 缓存命中率提升的三大工程技巧:教科书不会写的细节

单纯堆硬件解决不了命中率问题。我们靠三个反直觉技巧把命中率从71%拉到94.7%:

  • 技巧1:主动缓存“失败请求”
    传统思路只缓存成功响应,但我们发现:{"error": "rate_limit_exceeded"}这类错误响应,32%会在5分钟内被相同用户重试。我们将错误响应也存入缓存(TTL=300s),并标记is_error: true。当再次命中时,不直接返回错误,而是触发异步重试,并立即返回“稍等,正在重试中...”的友好提示。这招让用户感知的失败率下降58%,同时避免了重复的限流请求冲击上游。

  • 技巧2:缓存“半成品”而非“终稿”
    Agent常需多步骤:query→retrieve→reason→format。我们把每个步骤的中间产物都缓存:检索到的文档片段、推理的思维链草稿、格式化前的JSON。当用户修改query(如“把第三点换成更专业的说法”),系统直接复用前序步骤缓存,只重跑format环节。实测将多轮编辑场景的平均token消耗降低67%。

  • 技巧3:基于用户行为的缓存预热
    分析用户行为日志,发现83%的用户在打开Agent后,前3个操作高度固定(如“查余额”→“查明细”→“导出报表”)。我们在用户登录后,异步预热这组缓存。预热请求走低优先级队列,不影响主线程。上线后,新用户首屏加载时间从2.1s降到0.8s,首请求命中率从41%升至89%。

注意:预热不能盲目。我们设了严格阈值:只有连续7天、50+用户执行过相同操作序列,才触发预热。否则会制造大量垃圾缓存。

3.4 监控告警体系:不看这5个指标,等于没做缓存优化

我们部署了12个监控指标,但真正驱动决策的只有5个。每个指标都配了动态基线告警:

指标计算公式健康阈值异常时行动
全局命中率(Global Hit Rate)cache_hits / (cache_hits + cache_misses)≥92%<90%时自动触发缓存key分析任务
成本加权命中率(Cost-Weighted Hit Rate)Σ(hit * output_token_saved) / Σ(all_requests * avg_output_tokens)≥85%反映真实省钱效果,比全局命中率更重要
缓存新鲜度(Cache Freshness)avg( now() - created_at ) of top100 hits≤48h>72h说明缓存策略太保守,需缩短TTL
向量召回准确率(Vector Recall Accuracy)# of top3 candidates with jaccard_sim > 0.65 / 3≥75%<70%说明embedding模型或意图标签需优化
Token预算达成率(Budget Attainment)actual_tokens / budgeted_tokens0.85~1.05超出范围自动降级模型或截断

关键实现:所有指标都通过Prometheus暴露,告警规则用abs(avg_over_time(...[1h]) - avg_over_time(...[7d])) > 0.15检测突变,而不是静态阈值。因为业务有峰谷,昨天92%健康,今天91%可能就异常。

4. 常见问题与排查技巧实录:那些深夜救火的真实现场

4.1 “缓存命中率突然暴跌,但Redis监控一切正常”——如何30分钟定位?

这是最高频的P1故障。我们建立了一套标准化排查流水线:

Step 1:确认是否真暴跌
先查cost-weighted hit rate。如果它稳定,而global hit rate暴跌,说明是大量低价值请求(如心跳检测、空query)涌入,拉低了分母。这时看cache_misses{type="empty_query"}指标,果然发现监控脚本误配,每秒发100次""请求。

Step 2:区分是L1还是L2失效
查cache_hits{level="L1"}和cache_hits{level="L2"}。上周故障中,L1命中率99.2%→99.1%,L2从87%→32%。立刻聚焦FAISS集群。

Step 3:FAISS专项诊断

  • 查FAISS索引大小:index.ntotal。发现从2.1M突降至0.3M——索引重建失败。
  • 查重建日志:ERROR: faiss index build failed: memory allocation failed。原因为OOM Killer干掉了FAISS进程。
  • 根因:运维升级服务器内存后,未调整FAISS的faiss.omp_set_num_threads(1),导致多线程争抢内存。

Step 4:快速恢复

  • 临时切回L1+L3模式(损失部分语义命中,但保基本可用)
  • 重启FAISS服务,加载备份索引(我们每日凌晨全量dump)
  • 补丁:在启动脚本中强制设置export OMP_NUM_THREADS=2

排查口诀:先看成本加权指标,再分层隔离,最后查基础设施日志。永远假设“缓存系统本身没错,错的是它运行的环境”。

4.2 “Token账单暴涨,但API调用量没变”——五步归因法

某次财务对账发现Token消耗涨了220%,而OpenAI调用量只增8%。我们用这套方法定位:

  1. 按模型拆分:发现Qwen2-7B调用量涨300%,GPT-4-turbo持平 → 问题在国产模型路由。
  2. 按Agent拆分:92%增长来自“合同审查Agent” → 聚焦该服务。
  3. 查该Agent的input_token分布:P95从1200→4800 → 输入变长了。
  4. 抓取长输入样本:发现用户开始粘贴整页PDF文本(以前只传关键条款)→ 输入预处理模块未做长度截断。
  5. 验证修复:在预处理层加truncate_to_tokens(text, 2000, "qwen2"),账单回归正常。

关键工具:我们开发了一个token-profiler命令行工具,能对任意文本文件输出:

$ token-profiler --model qwen2-7b contract_v2.txt Input tokens: 4821 Breakdown: system_prompt=127, history=892, current_query=3802 Warning: current_query exceeds 3500-token threshold for cost control

4.3 “向量缓存总是返回不相关结果”——Embedding模型选型避坑指南

我们测试过7个Embedding模型,结论颠覆认知:

模型维度1k query耗时语义准确率*适用场景
text-embedding-ada-0021536120ms68%英文通用
bge-m31024210ms81%中英混合
bge-reranker-v2-m3768350ms92%高精度重排序
m3e-base76885ms73%中文快准
e5-mistral-7b-instruct40961200ms89%长文本

*注:语义准确率=人工标注1000个query-pair,计算top3召回中相关项占比

血泪教训:

  • 别用text-embedding-3-small做中文——它在中文语义空间坍缩严重,两个同义query向量夹角常>60°。
  • bge-reranker不是Embedding模型,而是Cross-Encoder重排序器,必须配合初筛(如BM25或粗粒度向量)使用。我们把它放在FAISS之后,对top50做精排,准确率从76%→92%。
  • 所有Embedding模型必须和LLM同源训练。用Qwen2-7B做LLM,就用bge-m3做Embedding,二者tokenization一致,避免语义鸿沟。

4.4 “缓存雪崩导致服务不可用”——熔断与降级的实战配置

去年双11,我们遭遇缓存雪崩:Redis集群CPU 100%,所有请求超时。根因是某个运营活动推送了带随机参数的URL,生成海量唯一key。

熔断策略(基于Resilience4j):

  • 当cache_get_latency_seconds_max{quantile="0.99"} > 500ms持续30秒,触发熔断。
  • 熔断后,所有缓存操作降级为return null,Agent直接走LLM fallback。
  • 熔断窗口:2分钟,期间每30秒尝试半开(允许10%请求走缓存)。

降级策略:

  • L1降级:关闭Caffeine,所有请求走L2。
  • L2降级:FAISS查询超时(>200ms)时,自动fallback到BM25关键词检索(用Elasticsearch)。
  • 最终兜底:当所有缓存不可用,启用static_fallback.json(预置高频FAQ的本地文件)。

关键配置:

resilience4j.circuitbreaker.instances.cache: failure-rate-threshold: 50 wait-duration-in-open-state: 120s ring-buffer-size-in-half-open-state: 10 automatic-transition-from-open-to-half-open-enabled: true

上线后,同类故障恢复时间从47分钟缩短到2分18秒。

5. 工程实践延伸:从“能用”到“好用”的三个进阶方向

5.1 缓存生命周期自动化:告别手动清理

我们开发了cache-governor服务,实现全生命周期管理:

  • 自动老化:根据hit_count和last_hit_at,用指数衰减公式计算retention_score = hit_count * e^(-0.001 * hours_since_last_hit)。每日扫描score<0.1的缓存,自动归档到冷存储(S3)。
  • 自动归档:归档时,将原始响应、query fingerprint、usage数据打包为Parquet文件,供后续成本分析。
  • 自动再生:当归档缓存被访问时,触发异步任务重新生成最新版缓存(用当前最新模型和prompt),替换旧版。

这套机制让缓存集群内存占用波动小于±3%,再也不用半夜起来手动redis-cli KEYS "agent:*" | xargs redis-cli DEL。

5.2 Token成本可视化:让每个工程师都看得懂的钱

我们把Token成本做成和代码覆盖率同等重要的工程指标:

  • IDE插件:VS Code插件实时显示当前Agent函数的预估token消耗(基于历史均值+query长度预测)。
  • PR检查:CI流水线中加入token-cost-check,当新增代码使单次调用预估token > 500时,阻断合并,要求作者提供优化方案。
  • Dashboard:Grafana看板展示“每千次请求Token成本趋势”,按Agent、模型、地域维度下钻。运营同学能直接看到“华东区用户提问更啰嗦,平均多花23token”。

实操心得:把成本指标“左移”到开发阶段,比事后审计有效10倍。我们上线此机制后,新功能的平均token消耗下降29%。

5.3 构建缓存健康度评分卡:量化评估每次优化的价值

每次缓存策略调整,我们都用统一评分卡评估:

维度权重评估方式示例
成本节约40%ΔToken消耗 × 单token成本-38.2% × $0.01 = $3782/日
性能提升25%ΔP95延迟(毫秒)-120ms → +25分
稳定性20%Δ缓存错误率-0.8% → +20分
可维护性15%代码行数变化 / 文档更新完整性-120行 + 新增README → +15分

总分≥85分才算成功优化。这个卡让我们拒绝了3个“命中率提升但成本暴增”的伪优化方案。

我个人在实际操作中发现,最有效的缓存优化往往来自最朴素的观察:盯着日志看10分钟,比读10篇论文更有用。上周我偶然发现,23%的缓存miss是因为用户在query末尾加了空格和换行——一个正则query.strip()就解决了。工程没有神话,只有无数个这样的小细节堆砌而成。当你下次看到缓存命中率数字时,不妨问问自己:这个数字背后,有多少个空格、多少个未清洗的IP、多少个未归一化的日期格式,在默默吞噬着你的Token预算。

版权声明: 本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
网站建设 2026/10/8 20:56:55

提示词工程实战:从结构化逻辑到三大框架与七类通用模板

之前有个朋友跑来跟我吐槽&#xff0c;说AI提示词没少看&#xff0c;越学越觉得玄乎。他照着网上某些“万能模板”写了一段&#xff0c;结果换个场景就完全失灵&#xff1b;我让他把提问方式发我一看&#xff0c;问题立刻暴露了——没有背景&#xff0c;没有目标&#xff0c;没…

作者头像 李华
网站建设 2026/10/8 20:56:06

Python 内置方法和属性详解

前言 Python 里凡是名字前后各带两条下划线的东西&#xff0c;例如 __init__、__repr__、__dict__&#xff0c;社区俗称「魔术方法」&#xff08;magic method&#xff09;或 dunder&#xff08;double underscore 的缩写&#xff09;。它们不是给程序员随便调用的&#xff0c;…

作者头像 李华
网站建设 2026/10/8 20:55:44

Spring Boot+MyBatis-Plus农业种植基地管理系统开发实战

1. 项目梳理与整体设计思路1.1 这个系统到底要解决什么问题先说个场景。我去过不少中小规模种植基地考察&#xff0c;发现它们的生产管理模式还停留在“本子记、口头传”的阶段。种什么、种在哪块地、什么时候施肥、打了什么药、这批货出了多少、卖给谁了&#xff0c;全靠一线工…

作者头像 李华
网站建设 2026/10/8 20:52:26

AI赋能iOS开发:从编码助手到端侧智能的实战指南

早上到工位&#xff0c;打开 Xcode&#xff0c;在 SwiftUI 文件里敲下一个Observable class&#xff0c;AI 自动把后面十几行属性、网络请求甚至单元测试的骨架都补了出来。这是我过去半年的真实工作状态。人工智能在 iOS 开发里&#xff0c;早就不是发布会上的 Demo&#xff0…

作者头像 李华
网站建设 2026/10/8 20:51:47

DFIG双馈风机单机无穷大Simulink仿真:建模、控制与调试全解析

刚把一台2MW双馈风机&#xff08;DFIG&#xff09;的单机无穷大仿真模型调稳定&#xff0c;趁热把这套系统的底细捋一捋。双馈风机仿真&#xff0c;入门容易&#xff0c;跑通也容易&#xff0c;但想跑出“可信”的结果&#xff0c;让波形能对上物理规律&#xff0c;让控制参数有…

作者头像 李华
网站建设 2026/10/8 20:50:58

括号匹配与动态规划:统计合法括号子串的线性DP解法

1. 先把题目读懂&#xff1a;什么是“永远在一起”上个月我们这边打了一场月赛&#xff0c;T2 就是这道 P15445&#xff0c;题面起了个非常文艺的名字叫“永远在一起”。我当时看到这个名字愣了一下&#xff0c;读完题意才发现&#xff0c;它本质上是在问括号匹配的问题&#x…

作者头像 李华