hiho一下第五周 數字三角形

hiho一下第五周 數字三角形

題目1：數字三角形

【題目解讀】

最基礎的動態規劃，提示中對於可以使用動態規劃的基本條件說明，感覺非常好：

（1）無後效性：“無論我是通過怎麼樣的方式到達第i層第j個房間的，我之前做出的選擇不會對我之後的選擇做出限制與優待。就像如果我規定至少要向右走3次，那麼狀態就不僅僅是(i, j, k)這樣，還要加上一個已經向右走的次數，那麼你覺得還能就直接像我們之前的方法進行計算麼？如果到達第i層第j個房間的路上向右走過3次了，那麼之後的走法就沒有任何限制，不然就仍會有一個至少要向右走一定次數的限制。”

（2）重復子問題：“我們將從起點出發到走出迷宮的最優路分解成了兩個子問題，其一是從第2層的第1個房間走出迷宮的最優路，其二是從第2層的第2個房間走出迷宮的最優路，只要能算出這兩個部分的最優值，我就可以知道從起點出發到走出迷宮的最優路。”小Hi道：”而按照這樣的方法，這兩個子問題都有一個相同的子問題——從第3層的第2個房間出發走出迷宮的最優路。””

【編寫細節】

DP最難的是邊界處理部分，一般都是

（1）best[0][0] 單獨處理，n=1 時單獨處理；

（2）本題中，三角形最左側一列、最右側一斜列，需要單獨處理。

【AC代碼】

#include
#include
#include

int reward[101][101];
long best[101][101];

long max(long a, long b)
{
	if(a>b) return a;
	else return b;
}

int main()
{
	int n;
	scanf(%d, &n);
	memset(reward, 0, sizeof(reward));
	memset(best, 0, sizeof(best));
	
	for(int i=0; i