科技公司 SWE 在线评估：能自己推出来的动态规划
SWE Online Assessment: Dynamic Programming You Can Actually Derive
维护站点的编辑标准、披露规则，以及归档和活跃内容的修订流程。
摘要 Summary
动态规划让人觉得难，往往是因为大家在背题解，而不是自己推。这篇文章给一套可复用的四步法——定义状态、写出转移、定好边界、选好计算顺序——并用一个干净的爬楼梯 / 凑硬币例子把它走一遍。
Dynamic programming feels hard because people memorise solutions instead of deriving them. This guide gives a repeatable four-step method — define the state, write the transition, set the base case, choose an order — and applies it to a clean climbing/coin example you can reuse.
动态规划一直背着「在线评估里最难那部分」的名声，但这种难度大多是自找的：大家总想着回忆某个具体题解，而不是把它推导出来。DP 在很多评估里占到约五分之一，而稳妥的通关方式，是一套几乎能套在任何 DP 题上的四步法——定义状态、写出转移、定好边界、选好填表顺序。
这篇文章整理自公开、广为人知的算法题型，而不是某家公司的真实原题。把它当成一张练习地图：先记住每种题的识别信号，每个模式手里留一份干净的参考解法，剩下的时间用来把题读懂，读到能一眼选对套路。
每一次都用的四个步骤| The Four Steps, Every Time
定义状态：用一句精确的话说清 dp[i]（或 dp[i][j]）到底代表什么。
写出转移：把某个状态的答案，用更小的、已经算好的状态表示出来。
定好边界：把最小的那些状态直接填好，不经过转移。
选好顺序：按某种次序填表，保证你依赖的每个值在用到时都已经算好。
怎么认出一道 DP 题| How to Spot a DP Problem
它问的是方案数、最小值或最大值，或者「能不能达成」。
贪心看起来很诱人，但你能举出一个让它失败的例子。
问题存在重叠子问题——同一个更小的问题被反复求解。
某个位置的答案，明显建立在更早位置的答案之上。
一个例子：凑出金额所需的最少硬币数| A Worked Example: Minimum Coins to Make an Amount
给定几种面额和一个目标金额，求凑出它所需的最少硬币数。设 dp[a] 为凑出金额 a 的最少硬币数。那么 dp[a] 就是在所有能用的硬币里，取最好的 dp[a - coin] 再加一。边界是 dp[0] = 0，并按金额从小到大填，保证每个更小的金额都已经算好。
def min_coins(coins, amount):
INF = float("inf")
# dp[a] = fewest coins to make amount a; dp[0] needs zero coins
dp = [0] + [INF] * amount
for a in range(1, amount + 1):
for coin in coins:
if coin <= a and dp[a - coin] + 1 < dp[a]:
dp[a] = dp[a - coin] + 1
return dp[amount] if dp[amount] != INF else -1四个步骤在这里都看得见：状态是 dp[a]，转移是 dp[a - coin] + 1，边界是 dp[0] = 0，外层从小到大遍历 a 定下了顺序。只要你能把这四件事讲出来，基本就能写出代码——而 INF 哨兵加上最后的 -1，干净地处理了「凑不出来」的情况。
最容易失分的几个点| Common Mistakes That Cost Marks
还没用一句话把状态定义清楚，就急着开始写代码。
填表顺序搞错，导致转移读到了一个还没算出来的值。
忘了处理无法达成或为空的情况，让 INF 或 None 泄漏进最终答案。
想当然地认为贪心捷径可行，却没测一个专门设计来打破它的用例。
一个够用的练习计划| A Focused Practice Plan
每道 DP 题，动手前先把四个步骤写成注释。
先从一维 DP（爬楼梯、凑硬币、打家劫舍）入手，再进到网格和字符串。
把一道你见过的题，从状态定义开始重新推一遍，不看代码。
练习用一句话解释转移方程——如果说不出来，说明你还没真正理解它。
常见问题 FAQ
为什么动态规划感觉比其他模式难那么多？
Why does dynamic programming feel so much harder than other patterns?
主要是因为大家在背成品题解，而不是自己推导。一旦你练熟了自己定义状态和转移，大多数 DP 题就变成了常规操作。
怎么判断一道题是 DP 而不是贪心？
How do I know a problem is DP and not greedy?
如果你能构造出一个输入，让「局部最优的选择」导致整体更差的答案，那贪心就失效了，你多半需要用 DP 来考虑各种选择的组合。
我该先学自顶向下的记忆化，还是自底向上的填表？
Should I learn top-down memoisation or bottom-up tables first?
两种都行。自底向上填表把计算顺序写得很明确，是个好习惯；自顶向下的记忆化往往更贴近递归定义。关键是学会在两者之间互相转换。
How This Article Was Produced
来源、审核和披露说明
- Source Type
- Editorially reviewed guidance built from public source material and manual synthesis.
- 基于公开资料和人工综合整理，并经过编辑复核的指南内容。
- AI Use
- AI-assisted drafting was used to organise notes and bilingual copy. A human editor reviewed structure, claims, and final wording before publication.
- AI 用于整理笔记和辅助双语表达。正式发布前，文章结构、关键判断和最终措辞均由人工编辑复核。
- What This Page Adds
- We condensed the material into decision-first guidance and surfaced the questions readers should answer before acting on the advice.
- 我们把资料压缩成以决策为先的指南，并补出了读者在采取行动前最该回答的关键问题。
For more on sourcing, corrections, and our recovery workflow, see Editorial Policy and Contact.
专题延伸阅读 Related Guides
按岗位方向、主题关键词和发布时间推荐，帮助读者从单篇文章进入完整准备路径。
SWE Online Assessment: Array and String Problems Made Approachable
科技公司 SWE 在线评估：数组与字符串题该怎么拆
Array and string questions are the single most common category in software-engineer online assessments. This guide explains the few patterns behind most of them — frequency counting, prefix sums, in-place editing, and single-pass parsing — and how to reach a clean, correct solution under time pressure.
SWE Online Assessment: Two Pointers and Sliding Window, From Scratch
科技公司 SWE 在线评估：双指针与滑动窗口从头讲清
Two pointers and sliding window turn many O(n^2) brute-force ideas into a single O(n) pass. This guide covers the three shapes you actually see — opposite ends, fast and slow, and a growing/shrinking window — with a clean example of the variable-size window that trips people up most.
SWE Online Assessment: Hash Map and Set Patterns
科技公司 SWE 在线评估：哈希表与集合题型精讲
Hash maps and sets buy you O(1) average lookups, and a surprising number of assessment problems are really about choosing the right key. This guide covers the complement trick, frequency maps, grouping by a signature, and using a seen-set to detect duplicates in one pass.
SWE Online Assessment: Graph and Tree Traversal Without the Panic
科技公司 SWE 在线评估：图与树的遍历不再慌
Graph and tree questions look intimidating but reduce to a small toolkit: BFS for shortest steps in an unweighted graph, DFS for exploring or counting connected regions, and level-order traversal for trees. This guide explains when to use each and a clean grid example most people can adapt.
Python Interview Prep for Data Science and Analytics: Solve the Common Patterns Cleanly
数据科学与分析岗 Python 面试：高频题不用炫技，先把常见模式写干净
Python interviews for data science and analytics roles usually focus on data handling, transformation, simple statistics, and whether you can explain your code. This guide groups the common challenge types and shows how to solve them cleanly without turning a straightforward task into something fragile.
Data Engineer Interview Guide: The Questions Behind SQL, Pipelines, and Reliability
数据工程师面试指南：SQL、管道和稳定性背后真正会被问什么
Data engineer interviews often look like a wall of unrelated questions until you group them by the decisions engineers actually make. This guide focuses on data modelling, pipeline design, operational reliability, and the judgement signals that separate a merely technical answer from a good engineering answer.