算法类型
一、贪心（Greedy）
理解和前端开发中的贪心
在每一步的选择中采取当前状态下的最优解，但无法保证全局最优解。
那我如何确保我做的题就适用于此？
解题策略在于，必须证明每一步所作的贪心选择最终导致问题的整体最优解。百度百科给出了全面的解释：证明过程大致是，首先考察问题的整体最优解，并证明可修改这个最优解，使其以贪心选择开始，做了贪心选择后，原问题的规模简化为规模更小的类似子问题。 然后用数学归纳法证明合理性。
对于前端开发来说，适用场景：
| 问题类型 | 贪心策略 | 经典例子 |
|---|---|---|
| 区间调度 | 每次选结束时间最早的 | 会议安排、无重叠区间 |
| 最小生成树 | Kruskal/Prim | 网络布线 |
| 哈夫曼编码 | 合并频率最小的两个节点 | 压缩算法 |
| 部分背包 | 按单位价值排序 | 货物装载（可切分） |
| 找零（特定面额） | 用最大面额优先 | 人民币/美元标准硬币 |
| 任务调度（单机） | 按最短处理时间优先 | 最小化平均等待时间 |
和DP的区别
贪心每一步局部最优解，不回溯；动态规划考虑所有可能，保留子问题结果。
两者都要求最优子结构，区别在于贪心要求更强的局部即可带来全局最优解，不满足时，只能用DP或回溯。
代表题
- placeholder
二、动态规划（DP）
概念
Dynamic Programming，一种记录历史，推导未来的算法，学科领域中属于运筹学的一个分支，是求解决策过程最优化的过程。把原问题拆解成相互重叠的子问题，并保存子问题的解（通常用数组/对象） ，避免重复计算，最终得到全局最优解或计数结果的方法。
记录历史，推导未来的算法——当前状态的值，由之前的一个或多个状态推导而来。它通常需要定义状态、写出状态转移方程、确定初始条件、按顺序计算。
核心三要素：
- 最优子结构：问题的最优解包含子问题的最优解；
- 重叠子问题：子问题被反复计算，DP用缓存(DP表)储存；
- 状态转移方程：描述如何从已知子问题推出当前问题的数学关系。
和贪心、分治的区别
- 贪心：只做一次选择，不保存子问题的结果；
- 分治：子问题不重叠（如归并排序），无记忆化；
- DP：子问题重叠 + 记录所有可能的选择结果。
前端开发中的DP应用
前端不像后端常做复杂的数学优化，但 DP 依然有大量用武之地，尤其是在交互、动态规划、性能优化、UI 状态计算中。
🌼动态表单/问卷的分数计算
场景：多步骤表单，每一步的选项影响后续分值，需要计算最优得分（如性格测试、风险评估）。
DP 用途：每个步骤作为阶段，保存到当前步骤的所有可能得分，避免穷举。
🌼字符串编辑距离（拼写检查、关键词高亮）
场景：用户输入搜索词，提示“您是不是要找 xxx”，或计算两个文本的相似度。
DP 算法：Levenshtein 距离，dp[i][j] 表示 word1 前 i 个字符转成 word2 前 j 个字符的最小操作次数。
🌼最长公共子序列（LCS）—— Git Diff、文本对比
场景：代码对比工具、富文本编辑器差异展示。
DP 用途：找出两个文本的公共部分，高亮差异。
🌼背包类问题在资源分配中的应用
场景：页面需要加载多个模块（图片、JS、CSS），总带宽/时间有限，选择哪些模块使收益最大（如广告曝光率）。
DP 用途：0-1 背包，dp[j] 表示容量 j 时最大价值。
🌼路线/导航类的最小代价
场景：2D 地图上从左上角到右下角的最小代价（每个格子有消耗），如 H5 游戏自动寻路。
DP 用途：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + cost[i][j]。
🌼分页/滚动列表的“可见区域最优渲染”
场景：长列表（虚拟滚动），需要提前计算哪些元素在可视区，以及滚动后需要加载的数据块。
DP 用途：不直接，但类似“区间调度”思想可结合 DP 决定缓存哪些块。
🌼前端路由权限组合（类似子集和问题）
场景：用户拥有若干权限，某个操作需要权限组合（比如任意两个权限即可），判断是否满足。
DP 用途：子集和问题的 DP 解法。
代表题
斐波那契数