这次在 HackerRank 上遇到了一套很经典的 Tiktok OA ，整套下来三道题，覆盖了 DP、完全背包以及 BFS 状态压缩三大板块。难度不算离谱，但对代码熟练度和细节把控要求比较高。如果平时刷题没注意过这些边界条件，现场很容易掉坑。下面就按照题目顺序来复盘一下。
Question 1 — Robot Paths with Landmines
Problem
A robot is moving on a grid of size n×mn \times mn×m. In one move, it moves one step right or one step down. Some cells of the grid have landmines, so the robot has to avoid them. The grid is given as an array of size n×mn \times mn×m, where 0 means landmine and 1 means safe cell. Find the number of ways to reach the bottom-right cell from the top-left cell, modulo 109+710^9 + 7109+7.
思路
典型 DP 模型：dp[i][j] 表示到达该点的路径数
如果当前 cell 是地雷，直接 dp[i][j]=0
转移公式：来自上方和左方的路径数相加
记得对结果 % MOD
核心代码 (Python)
MOD = 10**9 + 7
def findSafeWays(grid):
n, m = len(grid), len(grid[0])
if grid[0][0] == 0 or grid[n-1][m-1] == 0:
return 0
dp = [0] * m
dp[0] = 1
for j in range(1, m):
dp[j] = dp[j-1] if grid[0][j] else 0
for i in range(1, n):
dp[0] = dp[0] if grid[i][0] else 0
for j in range(1, m):
if grid[i][j] == 0:
dp[j] = 0
else:
dp[j] = (dp[j] + dp[j-1]) % MOD
return dp[-1]
小贴士
注意起点或终点为地雷的情况
可以用一维数组优化空间复杂度
大数运算一定要加 % MOD
Question 2 — Minimum Number of Umbrellas
Problem
Given the number of people needing shelter and a list of umbrella sizes, determine the minimum number of umbrellas required to cover exactly that number of people. If impossible, return -1.
思路
这是最少硬币数问题的变形（完全背包）
dp[t] 表示凑出人数 t 所需的最少伞数
初始化 dp[0]=0，其余设为无穷大
枚举每个伞的大小进行更新
核心代码 (Python)
def getUmbrellas(requirement, sizes):
INF = 10**9
dp = [INF] * (requirement + 1)
dp[0] = 0
for s in sizes:
for t in range(s, requirement + 1):
dp[t] = min(dp[t], dp[t-s] + 1)
return dp[requirement] if dp[requirement] < INF else -1
小贴士
注意是“完全背包”而不是 0/1 背包
也可以用 BFS 思路做最短路径，但 DP 更直接
如果 requirement 很大，DP 时间复杂度要留意（但题目给的上限比较友好）
Question 3 — Shortest Path to Collect All Coins
Problem
Chris must collect all gold coins in a maze and reach Alex. The maze is given as a 2D grid: 0=open, 1=blocked, 2=open+coin. Start at (0,0), Alex is at (x,y). Return the length of the shortest path to collect all coins and reach Alex, or -1 if impossible.
思路
本质是「最短路 + 必须经过所有金币」
用 BFS 扩展状态：(row, col, mask)，其中 mask 表示哪些金币已收集
当到达 (x,y) 且 mask 全满时返回步数
需要三维 visited 数组避免重复
核心代码 (Python)
from collections import deque
def minMoves(maze, ax, ay):
n, m = len(maze), len(maze[0])
coins, cid = {}, 0
for i in range(n):
for j in range(m):
if maze[i][j] == 2:
coins[(i,j)] = cid
cid += 1
full_mask = (1 << cid) - 1
start_mask = (1 << coins[(0,0)]) if (0,0) in coins else 0
visited = [[[False]*(1<<cid) for _ in range(m)] for __ in range(n)]
q = deque([(0,0,start_mask,0)])
visited[0][0][start_mask] = True
dirs = [(1,0),(-1,0),(0,1),(0,-1)]
while q:
i,j,mask,d = q.popleft()
if i==ax and j==ay and mask==full_mask:
return d
for dx,dy in dirs:
ni,nj = i+dx, j+dy
if 0<=ni<n and 0<=nj<m and maze[ni][nj]!=1:
nmask = mask
if (ni,nj) in coins:
nmask |= (1<<coins[(ni,nj)])
if not visited[ni][nj][nmask]:
visited[ni][nj][nmask] = True
q.append((ni,nj,nmask,d+1))
return -1
小贴士
BFS 状态要带上 mask，不然无法保证收集金币
如果金币数很多，可以改用“点对点最短路 + TSP DP”的解法
注意 Alex 的位置可能本身就是金币格，要在起始 mask 中体现
这套 OA 算是 HackerRank 平台上比较常见的组合：一道 DP 路径计数、一道完全背包变形、再加一道 BFS 状态压缩。整体思路不复杂，但细节多，尤其是边界和状态表示。如果能提前把这些模板敲熟，实战时就能省下很多 debug 时间。
OA备考与远程助攻服务
很多同学备战大厂 OA 的时候，总是卡在细节或者时间管理上。其实完全没必要一个人硬扛，我们可以帮你做全程的远程辅助：
- OA 实时助攻：HackerRank、CodeSignal、牛客网全覆盖
- 语音提醒 + 无痕联机：关键时刻帮你点出 bug，保证测试全 AC
- 面试辅助：VO、行为面试、系统设计都有实时提示
有需要的小伙伴可以随时联系我们，少踩一次坑，进下一轮的几率就能多一分。
