当前位置: 首页 > news >正文

最优/极值问题的算法选择

如何选择滑动窗口、二分、动态规划算法

刷leetcode时对于一些最优/极值问题往往不知采用哪一种算法,故借助大模型学习一些算法要点。


1. 滑动窗口(Sliding Window)

特点

  • 适用于 数组 / 字符串连续子区间 问题。
  • 目标通常是:区间内的最大/最小和、最长/最短长度、是否满足条件。
  • 要求窗口左右移动时能 快速更新答案(O(1) 或 O(log n) 更新)。

常见题型

  • 固定长度子数组的最大/最小和。
  • 至多 / 至少 K 个不同元素的子串问题。
  • 满足某个和 / 约束的最短或最长子数组。

关键词

连续子数组 / 子串 + 统计 / 优化


特点

  • 答案具有 单调性
    如果某个值 x 可行,那么 >x 或 <x 的区间整体也一定可行。
  • 通过 判定函数 check(mid) 来决定搜索方向。
  • 时间复杂度通常是 O(log n * f(n))

常见题型

  • 最小化最大值 / 最大化最小值
  • 分割问题(切木头、运货、分糖果)。
  • 阈值判定类问题(满足条件的最小时间 / 最大容量)。

关键词

最小化最大 / 最大化最小 + 判定函数单调


3. 动态规划(Dynamic Programming, DP)

特点

  • 状态之间有 重叠子问题最优子结构
  • 问题不能仅靠窗口滑动或单调性解决,需要逐步递推。
  • 常见于 序列问题 / 组合问题 / 路径问题

常见题型

  • 背包问题(01 背包、多重背包、完全背包)。
  • 最长子序列 / 编辑距离。
  • 区间 DP、树形 DP。
  • 棋盘/图上的最短路径或最大得分路径。

关键词

子问题重叠 + 递推关系明确


4. 贪心、搜索等算法待补充...


5. 快速判断流程

flowchart TDA[遇到最优问题] --> B{是否涉及连续子数组/子串?}B -->|是| C[考虑 滑动窗口 / 双指针 / 前缀和]B -->|否| D{答案是否具有单调性?}D -->|是| E[考虑 二分 + check 函数]D -->|否| F{问题是否有重叠子问题和最优子结构?}F -->|是| G[考虑 动态规划]F -->|否| H[尝试其他算法: 贪心 / 图论 / 搜索等]
http://www.hskmm.com/?act=detail&tid=21066

相关文章:

  • 第三方控件库的添加和使用
  • C4NR PVP服务器1.2 天穹炮塔更新
  • 树形dp [JOI Open 2020] 发电站 / Power Plant
  • 深入解析:灵画-AI绘画小程序
  • AT_arc156_b [ARC156B] Mex on Blackboard
  • 产品排序
  • 环形链表II-leetcode
  • ubuntu20.04安装nvidia显卡
  • [线段树系列 #6] 标记永久化
  • 9.29
  • c语言switch和if语句
  • Qt(制作一个方便的文本编辑器)
  • Java EE初阶启程记05---线程安全 - 指南
  • DataGridView表格控件使用说明
  • 题解:P7126 [Ynoi2008] rdCcot
  • 个人微信机器人开发api接口
  • MyBatis技术详解:从入门到高效开发 - 详解
  • 解码数据结构队列
  • 解决升级 Windows 11 24H2 后 NAS 共享无法显示的问题
  • 【还未找到原题】宝石(GEM) - Harvey
  • 第八篇
  • C# AStar 算法 - 实际应用
  • nocobase 源码安装
  • 航司网站url后缀参数FECU分析
  • 子网掩码完全指南:从入门到精通
  • 微信群机器人API
  • 9月29号
  • 【CF19E】Fairy - Harvey
  • Python从入门到实战 (14):工具落地:用 PyInstaller 打包 Python 脚本为可执行文件 - 实践
  • Harmony实现流转开发之音乐播放器跨设备流转 - 实践