演算法：Sums In A Triangle

最新 01-23

Example

Input:

2 1

1 2 3

1 2

4 1 2

2 3 1 1

Output:

這是一道面試題，首先考察我們閱讀英文文檔的能力，其次才是演算法。下面是我的譯文（如有錯誤，歡迎指出）：

讓我們思考一個關於三角形數的問題（第一行一個數字，第二行兩個數字，第三行三個數字…）,開發一個程序計算出從頂部到底部的路徑上，數字之和的最大數，具體規則如下：

*在每條路徑上，下一個數字位於下一行的正下方的數字或者下一行正下方的右邊的一位數字

*行數是可以增加的，但小於100

*所有的數都是0到99之前的正整數

輸入：

第一行的整數 n:測試用例的數量（大約為1000）

在 n個測試用例之後，是每個測試用例的行數和具體測試用例的內容

輸出：

每個測試用例的輸出值，各佔一行

這裡我給出自己的解題方式，而不是答案，由於面試沒拿下，原因是沒看懂，很心痛，回來之後在百度上搜了一下，只有答案，沒有具體的思路，突然想起面試官讓我多接觸國外的技術社區和官方的文檔（我一般沒有看國外文檔的習慣），爬梯上去之後，Google一下，果然有解題教程，在YouTobe上老外錄製了一個小視頻，分析的特別清楚，我仔細看了兩遍，關鍵的地方停下來，自己畫了畫，終於解決了這道題，這道題並不難，主要考的還是英文閱讀能力，希望對大家以後的學習有幫助！因為考慮到大家觀看不方便，我做了一次搬運工，把視頻教程放到我的頭條號上了，這是鏈接：http://www.365yg.com/group/6486638752071418382/

總結：

這道題採用了動態規劃演算法：

通過拆分問題，定義問題狀態和狀態之間的關係，使得問題能夠以遞推（或者說分治）的方式去解決。

最後還是把答案寫出來吧：

運行結果：

11-12 01:41:58.358 3481-3481/com.joe.mvvm E/MainActivity: index: 7

11-12 01:41:58.358 3481-3481/com.joe.mvvm E/MainActivity: index: 4

11-12 01:41:58.358 3481-3481//com.joe.mvvm E/MainActivity: index: 3

11-12 01:41:58.358 3481-3481//com.joe.mvvm E/MainActivity: index: 8

11-12 01:41:58.358 3481-3481//com.joe.mvvm E/MainActivity: index: 6

11-12 01:41:58.359 3481-3481//com.joe.mvvm E/MainActivity: index: 9

11-12 01:41:58.359 3481-3481//com.joe.mvvm E/MainActivity: SumsInTriangle: 9