题目要求 输入输出 输入：整数数组 nums nums[i] 表示第 i 间房子的金额 不能偷相邻房子 输出：返回最多能偷到的金额 约束：1 <= nums.length <= 100，0 <= nums[i] <= 400 示例 输入：nums = [1,2,3,1] 输出：4 解释：偷下标 0 和下标 2，金额 1 + 3 = 4 输入：nums = [2,7,9,3,1] 输出：12 解释：偷下标 0、2、4，金额 2 + 9 + 1 = 12 这篇只用 Python，从这个二选一冲突推出一维 DP。 从 [1,2,3,1] 的相邻冲突开始 看例子： nums = [1,2,3,1] 如果偷下标 2 的房子，金额是 3，那么下标 1 和下标 3 都不能偷。 如果不偷下标 2，答案可能来自前面下标 0..1 的最优结果。 所以走到某一间房时，核心选择只有两个： ...

题目要求 输入输出 输入：整数 n 含义：爬到第 n 阶楼顶 每次可以爬 1 或 2 阶 输出：返回到达楼顶的不同走法数量 约束：1 <= n <= 45 示例 输入：n = 2 输出：2 解释：1+1，2 输入：n = 3 输出：3 解释：1+1+1，1+2，2+1 这篇只用 Python，从 dp[i] 的含义一步一步推出最终代码。 从 n = 3 的最后一步开始 先看最小能暴露转移的例子： n = 3 到第 3 阶的最后一步只可能来自： 第 2 阶，再走 1 阶 第 1 阶，再走 2 阶 所以“到第 3 阶的方法数”不是凭空算出来的，而是来自两个更小的位置。 Step 1：先定义更小的问题 直接问“到第 n 阶有几种走法”太大。先定义： dp[i] = 到达第 i 阶的方法数 注意这里的 i 是楼梯位置，不是数组下标含义上的第几个元素。 ...

题目要求 输入输出 输入：整数数组 cost cost[i] 表示踩到第 i 阶的代价 每次可以爬 1 或 2 阶 可以从下标 0 或下标 1 开始 输出：返回到达楼顶的最小花费 约束：2 <= cost.length <= 1000，0 <= cost[i] <= 999 示例 输入：cost = [10,15,20] 输出：15 解释：从下标 1 开始，付 15 后直接到达 top 输入：cost = [1,100,1,1,1,100,1,1,100,1] 输出：6 从 [10,15,20] 的 top 位置开始 先看最小例子： cost = [10,15,20] 楼顶不是下标 2，而是在最后一阶之后的位置，可以记为位置 3。 到达 top 位置 3 的最后一步只可能来自： 位置 2，付 cost[2] 位置 1，付 cost[1] 这题最容易错的地方就在这里：我们要求的是“到达 top 的花费”，不是“到达最后一个下标的花费”。 ...

题目要求 输入输出 输入：整数数组 nums 输出：返回连续非空子数组的最大和 子数组必须连续 至少选一个元素 约束：1 <= nums.length <= 10^5，-10^4 <= nums[i] <= 10^4 示例 输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：[4,-1,2,1] 的和最大，为 6 输入：nums = [1] 输出：1 这篇只用 Python，从 dp[i] 的含义一步一步推出 Kadane 算法。 从 [-2,1,-3,4] 的断点开始 看一个前缀例子： nums = [-2, 1, -3, 4] 如果走到 4，有两种选择： 把前面的某个连续子数组接到 4 前面 从 4 自己重新开始 这里的关键不是“所有子数组怎么枚举”，而是： 当我们决定一个最优子数组必须以当前位置结尾时，它的来源只有两种：接上前一个位置的最优结尾，或者从当前位置重新开始。 这就是一维 DP 的入口。 Step 1：先定义一个更小的问题 直接问“整个数组的最大子数组和是多少”太大。我们先强加一个限制： 如果子数组必须以第 i 个元素结尾，它的最大和是多少？ 这个值记为 dp[i]。 这里的 dp[i] 不是“前 i 个元素里的最大子数组和”。它更窄： ...

题目要求 输入输出 输入：nums，长度 1 <= nums.length <= 10 元素范围：-10 <= nums[i] <= 10 所有元素互不相同 输出：返回 nums 的所有可能子集 顺序：结果顺序不限，子集内部不需要考虑排列顺序 示例 输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 这篇只用 Python 构造一个最小可运行解法。 从 [1,2] 的搜索树开始 最小但有分叉的例子是： nums = [1,2] 答案应该是： [], [1], [1,2], [2] 注意这里没有 [2,1]。这说明问题不是“随便排列所有选择”，而是“每个元素选或不选，且同一组元素只出现一次”。 如果把构造过程画成树： [] |- [1] | |- [1,2] |- [2] 这棵树暴露出两个事实： 每个节点都是一个合法子集。 进入 [1] 之后，后面只能继续看 2，不能回头再选 1 或生成 [2,1]。 Step 1：先说清楚一个递归层在解决什么 如果当前已经选出一个 path，剩下的问题是： 从某个起点之后的元素里，继续选择若干个元素，扩展当前 path。 这个“某个起点”必须被记下来。否则 [1,2] 和 [2,1] 会从不同路径重复出现。 先写最小骨架。它只保留两个状态： ...

题目要求 输入输出 输入：nums，长度 1 <= nums.length <= 10 元素范围：-10 <= nums[i] <= 10 nums 可能有重复元素 输出：返回所有不重复子集 顺序：结果顺序不限，但同一个值序列的子集只能出现一次 示例 输入：nums = [1,2,2] 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]] 这篇只用 Python，从一个能跑但浪费的版本，一步一步过渡到排序 + 层内去重。 从 [1,2,2] 的重复分支开始 最小能暴露问题的例子是： nums = [1,2,2] 如果直接照搬 78. 子集 的模板，搜索树里会出现两条不同分支： 选择下标 1 的 2 -> [2] 选择下标 2 的 2 -> [2] 这两个分支路径不同，但值序列相同，最终答案重复。 所以这题真正新增的问题不是“会不会回溯”，而是： 怎样跳过重复分支，同时保留 [2,2] 这种合法答案？ Step 1：先复用 78 的状态，看看哪里会坏 当前部分答案仍然需要 path；当前层仍然需要 start 控制只能往右选。 先写出 78 的核心版本： def dfs(start: int) -> None: res.append(path.copy()) for i in range(start, len(nums)): path.append(nums[i]) dfs(i + 1) path.pop() 这个版本在 nums 全部互不相同时是正确的。 ...

副标题 / 摘要 这篇文章专门解释一个关键过渡：为什么 fixed-length 的 seq2seq 很快会不够用，attention-based seq2seq 是怎么补上“按需读取源序列”这个能力的，以及这个思路为什么几乎会自然长成 Transformer。最后会收束到一份最小可运行的 PyTorch GRU + additive attention 实现。 从“苹果”为什么老翻不准开始 还是用这个最小翻译任务： src: <bos> I really love green apples <eos> tgt: <bos> 我 真的 喜欢 青 苹果 <eos> 当 decoder 走到要生成“苹果”这一步时，最理想的行为其实很明确： 它应该重点回头看源序列里的 apples 它可能顺手也看一眼 green 它不能只依赖一个已经被反复压缩过很多轮的最终隐藏状态 如果你用上一篇里那个最小 seq2seq： encoder 把整句读完 只把最后一个 hidden_enc 交给 decoder decoder 后面每一步都只靠这个固定长度状态和自己的历史 那么句子一长，这里就会出现一个很具体的问题： decoder 明明需要“现在按需去看源序列的某几个位置”，但 fixed-length seq2seq 只给了它“一次性打包好的整句摘要”。 这就是 attention-based seq2seq 出现的真实压力。 它不是为了“概念更高级”，而是因为 decoder 在每个时间步都需要重新决定自己该看源序列的哪里。 快速掌握地图 fixed-length seq2seq：encoder outputs -> 丢弃大部分，只保留 final hidden attention-based seq2seq：decoder step t -> 对所有 encoder outputs 打分 -> 加权求和得到 context_t 核心收益：不同目标位置可以读取不同源位置 仍然存在的限制：encoder 和 decoder 还是循环结构，时间上依然串行 通向 Transformer 的关键桥：decoder state 作为 query，encoder outputs 作为 memory 这篇文章重点深挖的两个概念 对齐分数与上下文向量：decoder 怎样在每一步决定“该看源序列哪里” 从 attention-based seq2seq 到 Transformer 的结构映射：哪些东西被保留了，哪些东西被替换了 大师级心智模型 fixed-length seq2seq 的核心假设是： ...

副标题 / 摘要 这篇文章不把 seq2seq 和 encoder-decoder 当成术语表来讲，而是从一个最小翻译任务出发，解释为什么“输入一段序列、输出另一段序列”会自然逼出编码器和解码器的分工，最后收束成一份最小可运行的 PyTorch GRU 实现。 从一个最小翻译任务开始 假设源序列是： <bos> I love apples <eos> 目标序列是： <bos> 我 喜欢 苹果 <eos> 当模型要生成“苹果”时，它至少要解决三件事： 它必须知道整句英文大意，而不只是当前一个词 它必须记住自己前面已经生成了“我 喜欢” 它必须按顺序一个词一个词地产生输出，而不是一次吐出整个目标序列 如果你只用一个普通分类器把源句子映射成一个类别，这个任务做不成。 因为这里的输出不是一个固定标签，而是长度可变的目标序列。 所以这里天然会逼出一个更具体的数据流： 先把源序列读完，压成可传递的状态 再从 <bos> 开始，逐步生成目标序列 每生成一步，都要同时依赖“源侧信息”和“目标侧历史” 这就是 sequence-to-sequence 的最小问题形态。 seq2seq 说的是任务：输入一段序列，输出另一段序列。 encoder-decoder 说的是实现：先编码输入，再逐步解码输出。 下面不先堆名词，直接按这个压力把代码一步一步长出来。 快速掌握地图 问题形态：src -> encoder -> hidden/context -> decoder -> logits 核心目标：学习条件概率 p(y_t | y_{<t}, x) 最小实现：Embedding + GRU Encoder + GRU Decoder + output projection 何时适用：翻译、摘要、改写、问答这类“输入序列 -> 输出序列”任务 明显局限：如果所有源信息都被压进一个固定长度向量，长句子会吃力 这篇文章重点深挖的两个概念 隐藏状态交接：encoder 到底把什么交给 decoder 右移目标序列与 teacher forcing：训练时 decoder 为什么不能直接喂完整真实答案 大师级心智模型 这类模型的核心抽象不是“两个 RNN 拼起来”，而是： ...

副标题 / 摘要 这篇文章不把 Transformer 当成一个现成黑盒来介绍，而是直接从一个最小翻译任务开始，让需要的结构一层一层长出来，最后收束成一份最小可运行的 PyTorch encoder-decoder Transformer。 从一个最小翻译任务开始 假设源序列是： <bos> I love apples <eos> 目标序列是： <bos> 我 喜欢 苹果 当模型要生成“苹果”时： 它不能看目标序列里未来还没生成的位置 它需要重点读取源序列中的 apples 它可能还需要参考前面的“我 喜欢”来决定当前词 所以这里天然会逼出三件事： 目标侧必须有因果约束 源侧和目标侧都需要全局读取 解码器不仅要读自己，还要读编码器输出 RNN 和 CNN 也能处理序列，但它们在长距离依赖和全并行训练上都有明显限制。 所以这里真正要解决的，不只是“做一个更深的网络”，而是让任意位置能直接交互，并且显式控制信息流方向。 下面开始按这个压力一步一步长代码。 Step 1：先有输入表示，但先不谈注意力 先看一个已经分词并编号后的最小输入： <bos> I love apples <eos> -> [1, 15, 982, 204, 2] 这里的 1, 15, 982, 204, 2 还不是模型已经理解后的表示。 它们只是词表里的编号，作用更接近“标签”或“学号”： 15 比 204 小，不代表它们语义上更接近 直接拿这种离散编号去做线性变换或点积，含义也不对 所以第一步只解决一个更具体的问题： 怎样把“词表编号”变成“模型后面可以继续计算的一组连续数值”？ 这里再引入两个词： token id：分词后查词表得到的离散编号 embedding：把每个离散编号映射成长度为 d_model 的可学习向量 先写最小版，不额外引入别的机制： ...