1.題目描述
上圖給出了一個數字三角形。
從三角形的頂部到底部有很多條不同的路徑。
對于每條路徑，把路徑上面的數加起來可以得到一個和，你的任務就是找到最大的和。
路徑上的每一步只能從一個數走到下一層和它最近的左邊的那個數或者右邊的那個數。
此外，向左下走的次數與向右下走的次數相差不能超過?1。
2.輸入格式
輸入的第一行包含一個整數?N，表示三角形的行數。
下面的?N?行給出數字三角形。
數字三角形上的數都是?0?至?100 之間的整數。
3.輸出格式
輸出一個整數，表示答案。
4.數據范圍
1≤N≤100
5.輸入樣例
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
6.輸出樣例
27
7.思路
動態規劃
1.狀態表示 ：f[i][j]表示所有從頭開始往下走到第i層第j個的路徑的最大值
2.狀態計算 ：f[i][j] = max(f[i-1][j],f[i-1][j-1]) + value[i][j];
8.代碼
#include<iostream>
using namespace std;
const int N = 110;
int n;int f[N][N];
int value[N][N];
int main()
{scanf("%d",&n);for(int i = 1; i<=n; i++)for(int j = 1; j <=i; j++)scanf("%d",&value[i][j]);for(int i = 1; i<= n; i++)for(int j = 1; j <=i; j++)f[i][j] = max(f[i-1][j],f[i-1][j-1]) + value[i][j];//n為偶數時，最后一層落在的點一定在n/2或n/2+1//n為奇數時，最后一層落在的點一定在n/2+1if(n % 2 == 0) printf("%d\n", max(f[n][n/2],f[n][n/2+1]));else printf("%d\n", f[n][n/2+1]);return 0;
}
