如何用編程 get 百萬年終獎？
2018 年 CSDN 軟體開發者大調查活動開始了！自 2004 年開始，我們通過對開發人員、開發技術以及開發工具、平台的狀況和發展趨勢等進行深入的調研，為開發者呈現了一幅幅真實的中國開發者畫像。十四年的歲月沉澱，萬餘人的濃墨重彩。相信有你的參與，會讓這幅開發者繪卷更加精彩。「Stay hungry, stay foolish」——Just join us now！
（繼續下滑，閱讀精彩內容吧 ）
作者| channingbreeze
責編 | 胡巍巍
小史是一個應屆生，雖然學的是電子專業，但是自己業餘時間看了很多互聯網與編程方面的書，一心想進BAT互聯網公司。
今天小史又去了一家互聯網小巨頭公司面試了。
面試現場
小史眉頭一皺，發現事情並不簡單。
題目：在數字矩陣中，從左上角到右下角，每次只能向右或向下，如何規劃路徑，能獲得最大數字總和？
小史開始仔細分析問題，一時間竟想不到很好的方法。
小史心中反覆默念題目，進行思考。
小史仔細回憶起了呂老師教他的華容道搜索演算法。
請教大神
回到學校，小史把面試情況和呂老師說了一下。
呂老師：紅色和藍色兩條路都能到達中間的100這個點，但是很明顯，紅色的路拿到的獎金更多。所以藍色的路，後面不管再怎麼走，都不可能拿到最大的獎金數了。
呂老師：假設藍色路徑再往後走出一條綠色路徑是最大獎金，那麼我把藍色路徑替換成紅色路徑，紅色加綠色得到的獎金就比藍色加綠色得到的多呀。
記憶化搜索
小史：哦，我明白了，這樣我每搜到一個點，都可以和這個數比較，如果比它大，就更新這個數，繼續搜，如果比它小，就不搜了，直接剪枝。
理解了演算法之後，小史的代碼寫起來也是非常快，不一會兒就寫好了：
DeepFirstSearch.java：
Main.java：
運行結果：
記憶廣搜
呂老師：記憶深搜確實可以剪枝，但是假如有人刻意安排數字，把較小的數都安排在你先搜的路徑上，那麼你的計算量還是不會減少太多。
小史：還有這麼壞的人呢？不過你這樣一說我到想起來，深搜確實缺少一種「全局觀」，可能第一條路搜完了，再來看第二條路，發現更好，結果第一條路全白搜了。
理解了演算法之後，小史的代碼寫起來也是非常快，不一會兒就寫好了：
BreadthFirstSearch.java：
Main.java：
運行結果：
動態規劃
呂老師：小史，代碼寫得不錯，咱們再來看看廣搜的過程，其實就是在搜索的過程中從左上到右下計算出了best(i,j)，所以為啥我們不能直接算出best(i,j)呢？
理解了演算法之後，小史的代碼寫起來也是非常快，不一會兒就寫好了：
DynamicProgramming.java：
Main.java：
運行結果：
動態規劃解析
呂老師：狀態的定義要滿足幾個點，第一，問題的答案是某種狀態，或者可由狀態進行推導。第二，當前狀態可以由之前的狀態推導而來。
狀態壓縮
小史：哦，我知道了，這道題，如果按照斜線方向來計算，只需要保留一條斜線的狀態，就能計算出下一條斜線。所以之前的狀態就不需要保留了。
理解了演算法之後，小史的代碼寫起來也是非常快，不一會兒就寫好了：
DpCompressed.java：
Main.java：
/**
* @author xiaoshi on 2018/10/20.
*/
publicclassMain{
publicstaticvoidmain(String[] args){
int[][] matrix1 = {
{300,500,560,400,160},
{1000,100,200,340,690},
{600,500,500,460,320},
{300,400,250,210,760}
};
int[][] matrix2 = {
{300,500,2560,400},
{1000,100,200,340},
{600,500,500,460},
{300,400,250,210},
{860,690,320,760}
};
DpCompressed dp =newDpCompressed();
System.out.println(dp.getMaxAward(matrix1));
System.out.println(dp.getMaxAward(matrix2));
}
}
運行結果：
作者簡介：channingbreeze，國內某互聯網公司全棧開發。
聲明：本文為作者投稿，版權歸對方所有。作者獨立觀點，不代表 CSDN 立場。
微信改版了，
想快速看到CSDN的熱乎文章，
趕快把CSDN公眾號設為星標吧，
打開公眾號，點擊「設為星標」就可以啦！
TAG:CSDN |