2026春招季刚刚开始各路笔试讨论群里最热闹的一道题就是开发岗3月15日这场的“搭房子”。我翻了不少复盘帖发现很多人不是被这题难倒而是被自己天马行空的贪心思路绊倒。这道题表面是排地块、选位置内核其实是非常典型的线性动态规划给你一排位置每个位置有收益附加“任意两栋房子下标差至少为k”的互斥约束问最大总收益。这篇文章把题意、模型抽象、状态转移再到Java、C、Python三种实现完整过一遍最后给出自测方法、对拍脚本和常见报错排查。不管你是正在准备校招还是想练练DP基础这篇都能拿来直接用。1. 先把“搭房子”翻译成算法模型1.1 题目长这样回忆版整理按考后回忆整理题面大概是这样的一条笔直的街道上有 n 个地块从左到右编号 1 到 n。第 i 个地块如果搭一栋房子可以得到收益 a[i]。注意a[i] 可能是负数说明这块地根本不合适盖房。你可以选择任意一些地块搭房子也可以一栋都不搭但是任意两栋房子所在位置的下标差必须至少为 k也就是两栋房子之间至少隔着 k-1 个空地。问能获得的最大总收益是多少。常见数据范围如下参数范围说明n1 ≤ n ≤ 10^5地块数量k1 ≤ k ≤ n两栋房子的最小下标间隔a[i]-10^9 ≤ a[i] ≤ 10^9单块地收益可能为负这个数据范围基本就把暴力解法卡死了。如果直接枚举所有选房子的方案子集个数是 2^nn 到 100 都跑不动更别说 10^5。所以题目考察的重点很明确要你把“选择互斥位置”这个问题抽象成状态用动态规划在 O(n) 时间内解决。1.2 为什么我劝你别贪心很多同学读完题的第一反应是既然每个位置有收益那就按收益从大到小排序然后一个一个选选了某个位置就把和它距离小于 k 的位置全部排除。听起来很合理但这题不是普通选数问题而是带位置约束的区间互斥问题贪心在这里一定会挂。看一组反例n 5k 2a [3, 4, 3, 2, 2]。按收益排序最大的收益是位置 2 的 4于是先选第 2 块地因为 k 2第 1、3 块地距离位置 2 都是 1必须排除。接下来剩下位置 4 和 5 的收益 2 可选但这两个位置距离 1只能选其中一个。贪心最终收益就是 4 2 6。但真正的最优解是选择位置 1、3、5收益 3 3 2 8。位置 1 和 3 下标差 2位置 3 和 5 下标差 2完全合法。贪心为了一个收益 4 的高点堵死了左右两个收益 3 的位置得不偿失。这就是区间互斥问题的典型结构为了让出空间经常要为了两个“中等收益”放弃一个“高收益”。还有同学想用双指针或者前缀和去维护“每 k 个位置里取最大值再累加”也不对。因为取完一个位置后它会污染两侧区间这种“污染”不是简单删掉一个点而是影响前后 k-1 个位置滑动窗口无法处理这种相互覆盖的关系。所以老老实实走DP。1.3 DP状态与转移一次讲透这道题只要想通一件事决定搭不搭第 i 个位置的房子时它对前方位置的影响是固定的不会影响后方因为后续决策只依赖前 i 个位置的最优值。定义 dp[i] 表示只考虑前 i 个地块时能获得的最大总收益。初始 dp[0] 0意思是前 0 块地一栋房子都不搭收益自然为 0。对于第 i 个地块只有两种选择。第一种不搭房子。前 i 个地块的收益就等于前 i-1 个地块的收益即 dp[i-1]。第二种搭房子。一旦在位置 i 搭了房子前面的房子必须在位置 i-k 或更早的地方否则距离不够。所以前面的部分只能从前 i-k 个地块中产生收益是 dp[i-k] a[i]。于是转移方程就是dp[i] max(dp[i-1], dp[i-k] a[i])当 i-k 小于 0 时意味着位置 i 前面没有足够的地块来再放一栋房子此时 dp[i-k] 不存在等价于只有一栋房子的收益 a[i]。为了代码统一可以把 i-k 和 0 取最大值也就是用 dp[max(0, i-k)] a[i] 作为第二个候选值。为什么这个转移是正确的因为任意一个合法方案要么不包含位置 i要么包含位置 i。不包含 i 的方案必然在前 i-1 个地块里收益不会超过 dp[i-1]包含 i 的方案去掉 i 之后剩下的房子只能出现在前 i-k 个地块中且这些房子的内部约束已经由 dp[i-k] 保证。两种情况取最大值就能覆盖所有合法方案。这就是最优子结构。最终答案就是 dp[n]。2. Java、C、Python 三套代码直接抄2.1 C 版long long 和下标边界是第一道坎C 实现最需要注意的有两点数据范围必须用 long long下标必须处理好负数。先计算一下上界n 最多 10^5每个 a[i] 最多 10^9全选的话总收益最高是 10^14。这个值远超 int 的 21 亿上限所以 C 代码里所有存储收益的变量都必须是 long long。上代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin n k; vectorlong long a(n 1); vectorlong long dp(n 1, 0); for (int i 1; i n; i) { cin a[i]; int preIdx max(0, i - k); dp[i] max(dp[i - 1], dp[preIdx] a[i]); } cout dp[n] \n; return 0; }我用max(0, i-k)作为下标这样当 i k 时自动退回到 dp[0]省去单独写分支。前提是 k ≥ 1这时 preIdx 一定小于 idp[preIdx] 必然是已经算好的历史状态不会出现本轮自我依赖的问题。有一点要提醒#include bits/stdc.h是 GNU 扩展在一些本地 IDE 或非 GNU 环境可能不支持。如果你在牛客、力扣这类 OJ 上提交基本都支持但如果在自己电脑上用标准编译器建议改成包含iostream和vector的写法否则编译会报错。2.2 Java 版用 BufferedReader 扛住大数据量Java 笔试最常见的问题有两个一是用 Scanner 读 10^5 个数太慢二是 int 溢出。Scanner 本身是正则分词性能差在这种数据量下虽然不一定超时但碰上紧张的笔试环境能省则省。我用 BufferedReader StringTokenizer 来做输入代码也更通用。import java.io.*; import java.util.*; public class Main { // 读取n个数允许数字分布在多行 static long[] readArr(BufferedReader br, int n) throws IOException { long[] a new long[n 1]; int idx 1; while (idx n) { String line br.readLine(); if (line null) break; StringTokenizer st new StringTokenizer(line); while (st.hasMoreTokens() idx n) { a[idx] Long.parseLong(st.nextToken()); } } return a; } public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken()); int k Integer.parseInt(st.nextToken()); long[] a readArr(br, n); long[] dp new long[n 1]; for (int i 1; i n; i) { dp[i] dp[i - 1]; int preIdx Math.max(0, i - k); dp[i] Math.max(dp[i], dp[preIdx] a[i]); } System.out.println(dp[n]); } }这段代码里的readArr是我刻意加的。牛客、赛码这些平台经常把数组数字放在一行但偶尔也会换行如果只用一次readLine().split()去读遇到跨行就当场少读几个数。readArr用一个 while 循环把多行数据全部收进来属于笔试里值得养成习惯的稳健写法。Java 的 long 和 C 的 long long 一样都是 64 位足够存 10^14 的结果。如果你偷懒用了 int测试数据一大就会输出错误答案而且这种错误还不容易在样例上暴露。2.3 Python 版快读和负索引大坑Python 写算法题是出了名的简洁但也有两个必须注意的地方。第一是输入。Python 的input()在 10^5 数据量下非常慢最好一次性把全部输入读进来再切分。我用sys.stdin.buffer.read().split()返回的是字节串列表再映射成 int速度快很多。第二是负索引。如果你写成dp[i-k]当 i k 时i-k 是负数。这不会报错Python 的列表允许负索引它会从尾部开始数比如 dp[-1] 是 dp 的最后一个元素。这种错误极其隐蔽打印中间变量都难发现因为代码逻辑看起来完全正常但结果就是错的。看代码import sys def main(): data list(map(int, sys.stdin.buffer.read().split())) if not data: return n, k data[0], data[1] a [0] data[2:2 n] dp [0] * (n 1) for i in range(1, n 1): pre_idx max(0, i - k) dp[i] max(dp[i - 1], dp[pre_idx] a[i]) print(dp[n]) if __name__ __main__: main()用max(0, i-k)代替dp[i-k]彻底避免负索引问题。Python 的 int 没有溢出概念C 和 Java 需要的 long long 顾虑在这里不存在代码写起来更省心。性能方面O(n) 循环处理 10^5 个数据完全没问题实测大概 0.2 秒级别适合笔试环境。3. 变体题应对恰好M栋、环形地块与空间优化3.1 恰好搭M栋从一维到二维题目有时不会问“最多收益”而是问“如果必须恰好搭 M 栋房子最大收益是多少”。这时候一维状态就不够了因为“恰好 M 栋”是一个额外约束必须把已经搭了几栋记进状态里。定义 dp[i][j] 表示前 i 个地块恰好搭了 j 栋房子的最大收益。转移方式依然是两个分支位置 i 不搭房dp[i][j] dp[i-1][j]位置 i 搭房dp[i][j] dp[i-k][j-1] a[i]初始化 dp[0][0] 0其他 dp[0][j] 设为负无穷表示“前 0 个地块要恰好搭 j 栋房子”是不可能事件。最终答案 dp[n][M]。核心循环如下const long long NEG -(1LL 60); vectorvectorlong long dp(n 1, vectorlong long(M 1, NEG)); dp[0][0] 0; for (int i 1; i n; i) { for (int j 0; j M; j) { dp[i][j] dp[i - 1][j]; if (j 0 i - k 0) { dp[i][j] max(dp[i][j], dp[i - k][j - 1] a[i]); } } } cout dp[n][M] \n;这里的i - k 0判断不能省。一维 DP 里我用了max(0, i-k)来兼容 i k 的情况那是因为“搭了 i 之后前面可能一栋都没有”本身就是合法方案。但二维 DP 里如果 i - k 0前面根本放不下 j-1 栋房子必须禁止转移。3.2 环形地块破环成链的通用套路如果题面再加一句“街道首尾相连成环形”比如位置 1 和位置 n 相邻就会多一重限制不能同时选位置 1 和位置 n。环状问题有一个通用处理套路破环成链枚举第一栋房子选不选。假设位置 1 不搭房那问题退化成一条从 1 到 n 的链直接跑普通 DP。假设位置 1 必须搭房那么位置 2 到位置 k 这一侧、位置 n-k1 到位置 n-1 这一侧全被排除剩余区间从第 k1 个位置到第 n-k 个位置继续跑普通 DP。两种方案取最大值即可。这个技巧在打家劫舍III、打家劫舍IV这类环形变体里经常出现属于校招笔试的高频延伸建议记住这个模板。3.3 空间优化把 O(n) 压到 O(k)原题转移只依赖 dp[i-1] 和 dp[i-k]理论上不需要保留全部 n1 个 dp 值。可以用一个长度为 k1 的循环数组下标映射成i % (k1)。这样做有个坑普通数组的负数下标问题会变成循环数组的“旧值残留”问题。当 i k 时(i-k) % (k1)在部分语言里会是负数C 的负数取模结果不是自然下标必须写成((i-k) % (k1) (k1)) % (k1)才有意义而且取到的可能是上一轮留下的旧状态不是我们想要的 0。处理起来代码反而绕。我的建议是笔试中 n 到 10^5 级别一维数组的 O(n) 空间完全够用没必要冒险做循环数组优化。这个知识点更多是面试聊天时的加分项真让你手写反而容易出错。4. 在线测试与常见问题排查实录4.1 不会判题先写过暴力对拍写完 DP 之后最担心的不是“不会写”而是“写了但状态转移有漏”。验证方法很简单写一个暴力枚举所有子集的函数在小数据上和 DP 结果进行比较。这种对拍方法能让绝大多数隐藏 bug 现原形。暴力函数思路如下long long brute(vectorlong long a, int k) { int n a.size() - 1; long long best 0; for (int mask 0; mask (1 n); mask) { bool ok true; long long sum 0; int last -1000000000; for (int i 0; i n; i) { if (mask (1 i)) { int pos i 1; if (last ! -1000000000 pos - last k) { ok false; break; } sum a[pos]; last pos; } } if (ok) best max(best, sum); } return best; }对拍主程序里随机生成 n ≤ 15 的小数据a[i] 在 -5 到 5 之间随机k 在 1 到 n 之间随机跑上几千轮。如果暴力结果和 DP 结果不一致立刻打印出这组数据基本就是你转移方程写漏了。随机数据里加入负数很重要。a[i] 可以为负时“一栋都不搭”的答案 0 才是有意义的如果随机范围全是正数你很可能意识不到自己的代码已经悄悄把负数情况处理错了。4.2 典型错误速查表这里把我见过的错误集中整理成一张表逐个排查效率最高。错误类型症状原因修复方法int 溢出小数据过大数据崩总收益达到 10^14C/Java 全部用 long long / long负下标访问C 输出诡异或崩溃没处理 i-k 0用 max(0, i-k) 作下标Python 负索引不报错答案莫名错误dp[i-k] 用了负数下标先判断 i-k 是否非负贪心排序反例 [3,4,3,2,2], k2 挂区间互斥结构不支持贪心换 DP 模型输入跨行Java 只读到部分数据StringTokenizer 只消费一行用 while 循环读到底输出用错格式printf 输出乱码long long 用了 %d用 %lld其中 Python 负索引那个坑我专门强调一下。Java 和 C 访问负下标会直接抛异常或者未定义行为程序很容易暴露但 Python 会默默访问列表末尾代码不报错输出却错得离谱。调试半天发现是负索引的情况我见过太多。4.3 三组测试用例把你的代码当场验明正身写完代码别急着交先用下面三组用例做快速验证每组都对应一个易错点。第一组是刚才的反例验证贪心和 DP 的区别输入 5 2 3 4 3 2 2 输出 8第二组验证 k 1 的边界。k 1 意味着任意两栋房子下标差至少 1相当于所有位置都能搭正数全取即可输入 3 1 1 2 3 输出 6第三组验证负收益的情况。所有 a[i] 都是负数时最优策略是一栋都不搭答案应该为 0输入 4 2 -1 -2 -3 -4 输出 0三组都通过基本可以说明代码的核心逻辑没有问题。4.4 面试官可能追问的几个点这道题面试时大概率会被追问核心问题有这么几个第一为什么不能贪心需要能快速给出反例第二如果需要输出具体方案怎么做思路是额外维护一个方案数组dp 更新时记录是从 dp[i-1] 还是从 dp[i-k] 转移来的最后从 n 倒着回溯第三如果 a[i] 全为正数贪心是否可行这个问题表面是问正数负数的区别实际还是在考察你对区间互斥结构的理解答案依然是不可行因为互斥带来的“取舍冲突”和收益正负无关。这些追问本身就是脱掉题面外衣看你是否真的掌握了模型。我个人在实际笔试复盘里最大的感受是这道题的分水岭不在“会不会写 DP”而在“能不能识别出这是 DP”。看到“搭房子”“选位置”“距离限制”这些词第一反应应该是把约束翻译成状态转移而不是被生活化的题目描述带着跑。最后分享一个小技巧遇到“间隔至少 k”这类约束可以默念一句口诀——dp[i] max(dp[i-1], dp[i-k] w[i])。很多看似花哨的题剥开壳都是这个模型把这句吃透这一类题就稳了。