難度：★★★★
不得不說某公司真低調(diào)，這樣就不說是什么公司了。筆試的形式很簡單，兩道題仆嗦，在 3 天內(nèi)完成其中的一道。于是也就分享其中一道吧……
第一道題：最大價值鏈
這道題使我想起了以前在 POJ 里做過的一道題先壕。給定一個迷宮（矩陣）瘩扼，負(fù)值代表墻，從右下角開始垃僚，累加走過的路（不可回頭）集绰，直到走到最右邊（或者右上角）。并且谆棺，這個題還有一個『傳送』功能栽燕，當(dāng)向下穿越到上面的時候，當(dāng)前結(jié)果清零改淑，以下一步的方案計算收益碍岔。
這道題一看就是動態(tài)規(guī)劃的思想，但是怎么個動態(tài)規(guī)劃法朵夏，還是值得商量的蔼啦。一開始開錯題。由于不可以向左走侍郭，所以往右走就是自由的询吴。但是如果往上走或者往下走，下一步就不能是上一個動作的相反方向了亮元。
既然是動態(tài)規(guī)劃，那么我們就考慮一下狀態(tài)方程吧…… 設(shè)當(dāng)前坐標(biāo)為 $(x, y)$ 唠摹、方向為 $d$爆捞。那么遞推方程就是：
$$ F(x,y,d)= \begin{cases}
M_{(x,y)}+\max\{ F(i+1,j,0), F(i, j-1,1), F(i,j+1,2) \}, & d=0 \\
M_{(x,y)}+\max\{ F(i+1,j,0), F(i,j-1,1) \}, & d=1 \\
M_{(x,y)}\max\{ F(i+1,j,0), F(i,j+1,2) \}, & d=2
\end{cases} $$
并且，
$$ d = \begin{cases} 0, \text{from right} \\ 1, \text{from up} \\ 2, \text{from down} \end{cases} $$
好像有什么不對——還沒有考慮邊界的情況（穿越）勾拉，如果考慮穿越煮甥，而且不能走重復(fù)的路盗温，那么情況就復(fù)雜很多了。
那么我們再定義三個執(zhí)行條件：
- 如果沒有路了成肘，即遇到的方塊 $M_{(x,y)}=-1$ ：
- 如果在邊界卖局，返回 0 ；
- 如果不在邊界双霍，返回 -1 （死胡同）砚偶；
- 否則，
- 如果不在邊界洒闸，嘗試向上染坯、下、右的順序丘逸，按照上述狀態(tài)方程找路单鹿；
- 如果當(dāng)前是邊界，并且上一步?jīng)]找到路線深纲，則設(shè)置此刻最大的價值是自身仲锄；
- 如果在邊界，嘗試穿越湃鹊，并與上一步獲得的值對比儒喊，取最大值。
如果考慮上 $(x,y)$ 的穿越問題涛舍，那么就困難很多了澄惊。另外，穿越以后富雅，還可能出現(xiàn)走重復(fù)的路的可能掸驱。這樣就會導(dǎo)致死循環(huán)。因此没佑，這里要考慮的不僅僅是最大價值毕贼，還有非重復(fù)路線，即維護(hù)一個走過路線的集合蛤奢。
寫了近一晚才勉強(qiáng)跑出來鬼癣，Java 和 C++ 的非多值返回算法，使得這份代碼傳遞了很多『輸出參數(shù)』啤贩，調(diào)試很不容易……做完都不知道有沒有漏掉情況待秃。
小結(jié)
總的來說，這次筆試題很考算法的基礎(chǔ)知識痹屹、對細(xì)節(jié)的捕捉和縝密的邏輯章郁，這道題初看就是 Medium 類型的，但是實際上難度系數(shù)還是很高的志衍。
再感嘆一下暖庄，這家公司真的很低調(diào)聊替。
