经典算法

KMP算法用于在一个文本串 text 中查找模式串 pattern 是否出现，以及出现的位置。 它的关键点是通过 部分匹配表（前缀函数 / LPS数组） 来避免重复比较，从而将时间复杂度降低到 O(n + m)。

假设你正在爬楼梯。 需要 n 阶你才能到达楼顶。 每次你可以爬： 1 阶 2 阶 问： 一共有多少种不同的方法可以爬到楼顶？

给定： 一个容量为 W 的背包 n 个物品 每个物品有： 重量 weight 价值 value 要求： 在不超过背包容量的情况下， 让背包中的总价值最大。

“打家劫舍”是经典的动态规划（Dynamic Programming）问题。 题目描述： 一个小偷准备偷窃沿街的房屋，每间房屋都有一定金额。 由于相邻房屋安装了联动报警系统，因此不能连续偷两间相邻房屋。 求在不触发警报的情况下，最多能偷多少钱。

“最大子数组和”是经典动态规划问题，也叫： 连续子数组最大和 Kadane 算法（卡丹算法） 题目描述： 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

最长递增子序列（LIS）是经典动态规划问题。 题目描述： 给定一个整数数组 nums， 找到其中最长严格递增子序列的长度。 注意： 子序列不要求连续 但元素顺序不能改变

最长公共子序列（LCS）是经典的动态规划问题。 题目描述： 给定两个字符串 text1 和 text2，返回它们的最长公共子序列的长度。 注意： 子序列：可以不连续，但必须保持相对顺序 公共：必须同时出现在两个字符串中

编辑距离是经典的动态规划问题，也叫： Levenshtein Distance（莱文斯坦距离） 题目描述： 给定两个字符串 word1 和 word2， 计算将 word1 转换成 word2 所需的最少操作数。 允许的操作： 插入一个字符 删除一个字符 替换一个字符

“零钱兑换”是经典的动态规划（Dynamic Programming）问题。 题目描述： 给定不同面额的硬币 coins 和一个总金额 amount，求凑出该金额所需的最少硬币数。 如果无法凑出，返回 -1。 特点： 每种硬币可以使用无限次（完全背包问题） 求“最小值”

股票买卖”是经典贪心 / 动态规划问题。 题目通常有多个变种，这里先讲最基础版本： 给定一个数组 prices，其中 prices[i] 表示第 i 天股票价格。 你只能买入一次并卖出一次，求最大利润。 要求： 只能交易一次 必须先买后卖

前缀和是非常基础且高频的算法技巧，用于快速计算区间和。 核心思想： 用一个数组 preSum 预先记录“从起点到当前位置的累加和”，从而把区间求和从 O(n) 优化到 O(1)。

“最长无重复子串”是经典的字符串 + 滑动窗口问题。 题目描述： 给定一个字符串 s，找出其中不包含重复字符的最长子串的长度。 特点： 子串必须是连续的 不能包含重复字符 常用解法：滑动窗口（双指针）

“最小覆盖子串”是经典的滑动窗口 + 哈希计数问题。 题目描述： 给定字符串 s 和 t，在 s 中找出包含 t 所有字符的最短子串，如果不存在则返回空字符串。 特点： 子串必须覆盖 t 中所有字符（包括重复次数） 使用滑动窗口动态调整区间

“接雨水”是经典的数组 + 双指针 / 动态规划 / 单调栈问题。 题目描述： 给定一个非负整数数组 height，表示每个位置的柱子高度，宽度为 1。 计算下雨后能接多少水。