2016年的京东研发工程师笔试题放到今天来看很多人会觉得“过时了”。但我刷完牛客上这套《京东2016研发工程师编程题二》之后反而觉得它比很多新题更有复盘价值——整套题不考偏门模板核心就是动态规划、递推和等比数列求和恰好覆盖了校招笔试最常见的几个基础考点。这篇文章我把三道题逐个拆开讲讲题干怎么理解、代码怎么写、坑在哪里最后聊一点笔试做题顺序的经验。不管你现在是准备京东校招还是单纯刷题保持手感这套题都值得花一个晚上过一遍。1. 先把这套题的内容还原出来再谈它为什么值得刷1.1 三道题的一句话版本牛客网上收录的这套题题面都带点“小故事”干掉了包装之后核心就几句话上台阶从第1级楼梯出发每次可以跨1级或2级问到第m级一共有多少种走法。题目特别说明从第1级到第1级算0种走法。年终奖在一个6x6棋盘上每个格子里放一个价值不等的礼物从左上角出发每次只能向下或向右移动一格到右下角停止求沿途能拿到的最大礼物价值。抛小球小东和三个朋友从不同高度往下抛球每次落地后反弹到原高度的一半再落下问第n次落地时每个球经过的总路程是多少结果保留两位小数。三个题都来自生活场景没有繁杂的输入格式也没有奇怪的边界数据属于非常标准的“校招友好型”题目。1.2 2016年的题放在2025年还不过时吗先说结论核心考点完全不过时。现在很多公司的笔试题越出越长题干动辄几百字甚至还要先读一段业务背景。但真正拉分的还是你能不能把一个看似生活化的问题转化成递推方程、状态转移方程或数学公式。这套题恰好是这种能力的集中训练。上台阶考的是斐波那契递推年终奖考的是二维动态规划抛小球考的是等比数列求和。这三类知识在2025年的研发岗笔试里依然是高频考点只是换了个包装。所以不要因为题目老就轻视它老题反而更能暴露基础薄弱的点。1.3 难度分布和常见丢分点我用一张表总结一下三个题的整体情况题目核心考点难度评估最容易丢分的地方上台阶斐波那契递推简单m1边界、大数溢出年终奖二维DP中等偏易第一行第一列初始化错误抛小球等比数列求和中等偏易混淆“落地”和“反弹”从难度分布能看出来这套题没有故意为难人。它想考察的就是“基础模型能不能写对”而不是“会不会背冷门算法”。所以刷这套题的时候不要以AC为目标要以“一次写出无 bug 的代码”为目标这个要求比AC高一个档次。2. 上台阶一个边界就能拦住一半人的斐波那契题2.1 先厘清一个容易混淆的初值问题题目说的是“从第1级出发走到第m级”。很多人的第一反应是设 dp[i] 表示“从第1级走到第i级的走法数”然后写dp[1] 0 dp[2] 1 dp[i] dp[i-1] dp[i-2]这个初值一眼看过去没问题但手算到 dp[3] 就露馅了。dp[3] dp[2] dp[1] 1但实际上从第1级到第3级有两条路1 - 2 - 3 和 1 - 3。问题出在 dp[1] 这个值上如果把它当成计数起点它应该是1但题目规定“从第1级到第1级有0种走法”。更干净的做法是不要和题目规定硬刚转换一下模型。从第1级走到第m级本质上是“要跨过 m-1 段台阶”每次可以跨1段或2段。设 f[k] 表示跨过 k 段台阶的方案数f[0] 1 f[1] 1 f[k] f[k-1] f[k-2] (k 2)答案就是 f[m-1]。但是题目明确要求 m1 时输出0而 f[0]1所以代码里必须对 m1 做特判。2.2 用迭代替代递归顺便解决溢出焦虑如果 m 给到 80、90递归不做备忘录会直接指数爆炸。就算加了备忘录Python 默认递归深度也可能不够。所以笔试里遇到这种递推题第一选择永远是迭代。def count_ways(m: int) - int: if m 1: return 0 a, b 1, 1 # f[0]和f[1] for _ in range(2, m): a, b b, a b return b验证几个边界m 2 - 循环不执行返回 b 1 # 1-21种 m 3 - 循环执行一次返回 b 2 # 1-2-31-32种 m 4 - 循环执行两次返回 b 3 # 1-2-3-41-3-41-2-43种Python 的整数没有位数上限所以 m 稍微大一点也不会溢出。但如果你在笔试环境里用 Java 或 C就要注意了。Java 的 int 大约到 Fibonacci 第 46 项就会溢出long 大约到第 92 项。如果题目数据范围给到 90 以上Java 要上 BigIntegerC 得自己写大数加法或使用 unsigned long long 再注意边界。这个坑不理解递推本质的人很容易踩。2.3 输入输出和实际提交时的细节牛客这类平台通常输入是一个正整数 m输出是一个整数。如果题目有多组输入别忘了用 while 循环读取。import sys def solve(): data sys.stdin.read().strip().split() for token in data: m int(token) print(count_ways(m)) if __name__ __main__: solve()可能有朋友会问m1 这种用例真的会出现在测试数据里吗会。而且往往就藏在边界用例里。这种“题目用一句话告诉你从第1级到第1级有0种走法”的提示一定要当成考点来看待它不是废话。3. 年终奖6x6矩阵背后的二维DP其实可以滚动成一维3.1 为什么“只能向右或向下”这句话直接决定了算法选型如果网格中可以上下左右随意走这个问题就变成了带权图中的最长路径不能直接用 DP得做搜索。但题目明确限制了“每次只能向下或向右移动一步”这就意味着每个格子的前驱状态只有两个上方格子和左方格子。子问题之间不存在环天然满足动态规划的无后效性要求。这给我们的启发是拿到一个网格题先看移动方向。只要方向被限制为单调的“向右向下”或“向右向下对角线”第一反应就应该是 DP而不是深搜。深搜在这种题目上大概率超时而且代码写起来也复杂得多。3.2 状态转移和边界初始化的正确姿势设 dp[i][j] 表示从左上角走到棋盘第 i 行第 j 列时能拿到的最大礼物价值。由于只能向右或向下当前位置只能来自上方或左方dp[i][j] max(dp[i-1][j], dp[i][j-1]) board[i][j]边界条件不能漏dp[0][0] board[0][0]起点必然要拿。第一行元素只能从左边走过来所以 dp[0][j] dp[0][j-1] board[0][j]。第一列元素只能从上边走过来所以 dp[i][0] dp[i-1][0] board[i][0]。完整代码如下def get_most_gold(board): n len(board) m len(board[0]) dp [[0] * m for _ in range(n)] dp[0][0] board[0][0] for j in range(1, m): dp[0][j] dp[0][j-1] board[0][j] for i in range(1, n): dp[i][0] dp[i-1][0] board[i][0] for i in range(1, n): for j in range(1, m): dp[i][j] max(dp[i-1][j], dp[i][j-1]) board[i][j] return dp[n-1][m-1]注意千万不要把第一行第一列的初始化漏掉然后在内层循环里用 if i 0 or j 0 去处理。这样也能跑但代码会显得混乱也更容易在笔试紧张时写错。3.3 空间优化一维数组是怎么省下那一半内存的6x6的棋盘很小二维数组完全够用。但如果你在面试时主动提出“这个状态只依赖上一行和当前行左侧可以用一维滚动数组优化”会是一个明显的加分点。核心思想是外层循环遍历行内层循环遍历列dp[j] 在更新前保存的是上一行同列的值dp[j-1] 在当前轮已经更新成了当前行左侧的值。def get_most_gold_1d(board): n len(board) m len(board[0]) dp [0] * m for i in range(n): for j in range(m): if i 0 and j 0: dp[j] board[i][j] elif i 0: dp[j] dp[j-1] board[i][j] elif j 0: dp[j] dp[j] board[i][j] else: dp[j] max(dp[j], dp[j-1]) board[i][j] return dp[m-1]这段代码有四个分支看起来比二维版本繁琐但空间复杂度从 O(n*m) 降到了 O(m)。如果棋盘不是 6x6而是 1000x1000这个优化就是实打实的性能提升。3.4 这道题在笔试里最容易出现的三种错误第一个错误是方向条件看错把“只能向右向下”理解成“可以上下左右”然后去写搜索。这样不是不能做但代码量和出错概率都会增加在限时笔试里非常不划算。第二个错误是边界初始化写成0。如果 dp[0][0] 初始化为0而不是 board[0][0]第一行和第一列的结果会全部少算一个左上角的礼物价值导致最终答案偏小。第三个错误是只算到右下角却忘了路径上所有格子都要累加。有些同学会把 dp[i][j] 定义成“从左上角到当前格子的最大步数”或者“路径长度”而不是价值总和这就完全跑偏了。DP 题复盘的时候先确认状态定义再写转移方程顺序不能反。4. 抛小球会推导通项公式比会写循环多拿一个印象分4.1 看清“第n次落地”和“第n次反弹”的区别这道题最大的坑藏在题面措辞里。它问的是“从开始抛出到第n次落地时经过的总路程”不是“第n次反弹后经过的总路程”。这两个概念差一个反弹段结果完全不同。理解这个区别最好的办法是画一条时间线第一次落地球从高度 h 落下路程 h。第一次反弹球向上走 h/2。第二次落地球从 h/2 高度落下路程又增加 h/2。所以到第二次落地时总路程 h h/2 h/2 2h。注意这个过程里包含了第一次反弹但并没有计算“第二次反弹”。很多初学者会以为第二次落地总路程是 h h/2 1.5h这就是没分清“第几次落地”和“第几次反弹”。4.2 从第一次落地开始逐步推导通项公式先把前几次落地的总路程列出来找规律落地次数增加的路程总路程1hh2h/2 h/2 h2h3h/4 h/4 h/22.5h4h/8 h/8 h/42.75h从第二次落地开始每次新增的路程都是上一次新增的一半。因为反弹高度是等比递减的所以总路程是一个等比数列求和。设第 n 次落地的总路程为 S_nS_n h 2h/2 2h/4 ... 2h/2^(n-1) h h h/2 h/4 ... h/2^(n-2)对后面从 h/2 到 h/2^(n-2) 的部分求和得到S_n 3h - h/2^(n-2)这个公式对 n1 也成立因为 2^(-1) 0.53h - h/0.5 h。但为了代码可读性我建议还是先特判 n1再直接用公式避免指数为负数让其他语言的同事看不懂。4.3 Python实现与格式化输出def ball_distance(h: float, n: int) - float: if n 1: return h return 3 * h - h / (2.0 ** (n - 2)) def solve(): values list(map(float, input().split())) h1, h2, h3, h4 values[:4] n int(values[4]) for h in (h1, h2, h3, h4): print({:.2f}.format(ball_distance(h, n)))输入是四个高度和一个 n输出四行。这里有两个细节值得注意。第一不要把 n 也转成 float要先用 float 读四个高度再单独把最后一个转成 int。如果统一用 float 读入后面做指数运算时 n 可能被当作浮点数在某些语言里会出问题。第二输出保留两位小数Python 里用{:.2f}.format(x)最稳。不要用round(x, 2)它做的是银行家舍入遇到 0.005 这种边界情况可能和牛客的答案不一致。4.4 当 n 很大的时候模拟和公式的性能差异如果不推导公式用直接模拟反弹过程也能算出正确结果def ball_distance_simulate(h, n): total h height h for _ in range(1, n): height / 2 total 2 * height return total当 n 只有几十的时候模拟完全没压力。但笔试里一旦出现 n 等于 10^9 甚至更大模拟就会超时。而公式版本是 O(1) 常数时间不管 n 多大都能瞬间算出结果。在笔试答题时如果时间紧张写循环模拟拿部分分数是合理的策略。但如果想在面试环节拿高分最好在代码旁边或注释里写出通项公式的推导过程。这会让面试官觉得你不只会写代码还具备数学建模能力。5. 刷完这套题之后的笔试心得与延伸思考5.1 做题顺序怎么安排才不容易崩这套题里上台阶和年终奖都属于“一眼看得出模型”的题抛小球则需要一点数学推导。实际笔试时我会建议先花两分钟把所有题都扫一遍把“有把握的题”标记为先做把“可能卡住的题”放后面。为什么要这样因为笔试比的不只是会不会还比谁在有限时间内拿到的分多。如果一上来就死磕某道题很容易陷入“调不出来又不舍得放弃”的恶性循环。先把能拿的分全部拿到再回来啃硬骨头心态会稳很多。5.2 这三道题能给面试官留下什么好印象很多人以为面试官只关心AC结果其实他们更关心你的思考过程。在上台阶题里你可以