這次在 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 hasto 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 ofpeople. 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、行為面試、系統設計都有即時提示
有需要的小夥伴可以隨時聯繫我們，少踩一次坑，進下一輪的幾率就能多一分。
