寫的有點急可能有點亂，大家先将就下吧
題目：
描述:給定一個由n行數字組成的數字三角形如下圖所示。試設計一個算法，計算出從三角形的頂至底的一條路徑，使該路徑經過的數字總和最大。
程式設計：對于給定的由n 行數字組成的數字三角形，程式設計計算從三角形的頂至底的路徑經過的數字和的最大值。
輸入:從檔案(input.txt)中讀入資料的第1 行是數字三角形的行數n，1<=n<=100。接下來n行是數字三角形各行中的數字。所有數字在0..99之間。
輸出:程式運作結束時，将計算結果輸出到檔案(output.txt)。第1 行的數是計算出的最大值。
樣例輸入(input.txt)：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
樣例輸出(output.txt)：
30
分析：(不用動态規劃的前提下)
（1）單純貪心算法是無法實作的，因為貪心算法隻是局部最優，無法全局最優，是以不能用貪心算法的思路。
（2）我們隻要把每一行的最大值算出來，再有選擇的将此次的結果帶入下一次運算，應該就可以實作。
思路：
我是這樣想的，以上面用數字羅列的三角形為例，每一個數字的父節點隻可能是他左上方的或正上方的，是以隻要從第一行開始累積，每次都挑選出目前計算結果最大的，累加下來，備下一次用，直到最後，這樣應該就OK了，是以關鍵問題就是在二維數組中找到它邏輯上來說的左上發和正上方的數，也就是找到他們的坐标。左上是[row-1,line-1],正上[row-1,line]，一直累加到最後一行，再從最後一行中找出最大的數字，就是要的的結果了。
實作：
（這裡沒有動态去申請二位數字，直接一次性申請了100x100的數組，比較省勁，也沒浪費太多記憶體）
#include <stdio.h>
#include <stdlib.h>
int arr[100][100];
/****************************************************************
*函 數：int readfile(int * rowCount) *
*參 數：存儲有多少行的變量指針 *
*功 能：從檔案中讀取資訊并存儲資訊 *
*返 回：檔案讀取成功傳回1否則傳回0 *
*****************************************************************/
int readfile(int * rowCount)
{
FILE * file;
int loop = 0; //列循環變量
int circle = 0; //行循環變量
//以隻讀方式打開檔案并判斷打開是否成功
if(!(file = fopen("input.txt", "r")))
{
return 0;
}
fscanf(file, "%d", rowCount); //從檔案中讀數字（讀出第一個數字(行數)）
//循環讀取檔案中的數字(行計數)
for(loop = 0; loop < *rowCount; loop++)
{
//循環讀取檔案中的數字(列計數)
for(circle = 0; circle <= loop; circle++)
{
fscanf(file, " %d", &arr[loop][circle]); //繼續循環讀檔案中的數字，存儲進數組
}
}
fclose(file);
return 1;
}
/*****************************************
*函 數：int writefile(int maxNum) *
*參 數：待向檔案中寫入的最大數字 *
*功 能：向"output.txt"中寫入數字 *
*返 回：檔案寫入成功傳回1否則傳回0 *
******************************************/
int writefile(int maxNum)
{
FILE * file;
//以隻讀方式打開檔案并判斷打開是否成功
if(!(file = fopen("output.txt", "w")))
{
return 0;
}
fprintf(file, "%d", maxNum); //向檔案中輸入數字
fclose(file);
return 1;
}
/****************************************************************
*函 數：int getMax(int loop, int circle) *
*參 數：(父節點)所在行，所在列 *
*功 能：判斷指定行的指定列的前一個和目前數字中最大的并傳回 *
*返 回：傳回指定行的指定列的前一個和目前數字中最大的 *
*****************************************************************/
int getMax(int loop, int circle)
{
int num1, num2; //數字存儲變量
//判斷列數是否下越界
if(circle - 1 < 0)
{
return arr[loop][circle]; //存在越界，傳回另一個數
}
//列未越界
else
{
num1 = arr[loop][circle - 1]; //存儲此數
}
//判斷列數是否上越界
if(circle > loop)
{
return num1; //存在越界，傳回另一個書
}
//列未越界
else
{
num2 = arr[loop][circle]; //存儲此數
}
return num1 > num2 ? num1 : num2; //兩數都未越界，傳回最大的
}
/**********************************************************
*函 數：int getTrianglesMax(int rowCount) *
*參 數：三角形行數 *
*功 能：周遊每一層并傳回從頂到底路徑和的最大值 *
*返 回：所有路徑中最優路徑上數字和的最大值 *
**********************************************************/
int getTrianglesMax(int rowCount)
{
int loop = 1; //行循環變量
int circle = 0; //列循環變量
int maxNum = 0; //存儲最大數字
//數組行循環
for(; loop < rowCount; loop++)
{
//數組列循環
for(circle = 0; circle <= loop; circle++)
{
arr[loop][circle] += getMax(loop - 1, circle); //循環此列累加上此列對應上一行的的路徑的最大值
}
}
//循環查找最後一行中的最大值
for(--loop, circle = 0; circle < rowCount; circle++)
{
//判斷目前的循環的值是否比最大值大
if(maxNum < arr[loop][circle])
{
maxNum = arr[loop][circle]; //如果比最大值大，存儲目前最大值
}
}
return maxNum; //傳回最後獲得的最大值
}
/*********************
*函 數：int main() *
*參 數：無 *
*功 能：主函數 *
*返 回：0 *
*********************/
int main()
{
int rowCount = 0; //存儲行數
int maxNum = 0; //存儲所求最大路徑數值
//檔案讀取并判斷是否成功
if(!readfile(&rowCount))
{
puts("read file error.");
exit(0);
}
//讀取檔案成功
maxNum = getTrianglesMax(rowCount); //周遊數組并擷取最大路徑的和
//将結果寫入檔案并判斷檔案是否寫入成功
if(!writefile(maxNum))
{
puts("write file error.");
}
return 0;
}
總結：
其實很多問題可以不用動态規劃解決，可能複雜點，但是思路上比想公式要簡單得多。
![python算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)