目錄

邊讀邊存

優(yōu)化成一維數(shù)組——倒序沒(méi)用了？

從上往下存，最大值存在最后一行，最后遍歷最后一行得到最大值的寫法?

邊讀邊存

邊讀邊存，可以有效降低時(shí)間復(fù)雜度

#include<iostream>
using namespace std;
int dp[1005][1005] = { 0 };
//dp[i][j]表示前面的路徑(包括dp[i][j]點(diǎn)本身)能取得的最大值

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
//由于題目數(shù)據(jù)量較大，上面兩行代碼可以加速35%左右
	int r, j = 0, cnt = 2, MAX = -1;
	cin >> r;
	cin >> dp[1][1];
//下面的內(nèi)層循環(huán)比較特殊，因?yàn)闃?shù)每往下一層，元素都遞增一個(gè)
//所以用cnt來(lái)記錄每層元素的個(gè)數(shù)
	for (int i = 2; i <= r; ++i)
	{
		while (++j <= cnt)
		{
			cin >> dp[i][j];
			dp[i][j] += max(dp[i - 1][j], dp[i - 1][j - 1]);
//由于是二叉樹(shù)，因此每個(gè)節(jié)點(diǎn)只需判斷它前面兩個(gè)結(jié)點(diǎn)的值哪個(gè)最大即可
//因?yàn)槭菑膁p[1][1]開(kāi)始存入數(shù)據(jù)，所以i-1和j-1均不會(huì)越界
		}
		++cnt;
		j = 0;
	}
	//遍歷最后一行判斷誰(shuí)是最大值
	for (int i = 1; i <= r; ++i)
	{
		MAX = max(MAX, dp[r][i]);
	}
	cout << MAX;
	return 0;
}

優(yōu)化成一維數(shù)組——倒序沒(méi)用了？

在上一篇文章（【洛谷】采藥(01背包問(wèn)題)）將二維數(shù)組優(yōu)化成一維數(shù)組的過(guò)程中，內(nèi)層循環(huán)我們是采用倒序的方式計(jì)算dp[ i ][ j ]，這是因?yàn)槿绻虼鎯?chǔ)dp[ i ][ j ]，就會(huì)覆蓋掉dp[ i-1 ][ j ]，這樣就無(wú)法通過(guò)狀態(tài)方程計(jì)算dp[ i ][ j ]。在這道題中同樣要避免覆蓋掉dp[ i-1 ][ j ]，不過(guò)為了保證時(shí)間復(fù)雜度，必須保留邊讀邊存的做法。

接下來(lái)嘗試一下倒序的方式在這題中是否適用（這么問(wèn)了肯定不適用，正確答案請(qǐng)移步最后）

int r, j = 3, cnt = 2, MAX = -1;
	cin >> r;
	cin >> dp[1];
	for (int i = 2; i <= r; ++i)
	{
		while (--j >= 1)
		{
			cin >> dp[j];
			dp[j] += max(dp[j], dp[j - 1]);
		}
		++cnt;
		j = cnt;
	}

首先要注意一點(diǎn)，我們是逆序輸入，也就是說(shuō)如果原來(lái)輸入 3，10，9，那么在數(shù)組的里存放的順序應(yīng)該是9，10，3（假設(shè)單純的存進(jìn)去，不進(jìn)行運(yùn)算）

那么輸入的樹(shù)應(yīng)該是鏡像的，比如

7

3 8

8 1 0

2 7 4 4

會(huì)變成：

? ? ? ? ?7

? ? ? 8 3

? ?0?1 8

4 4 7 2

這兩棵樹(shù)在這道題中其實(shí)沒(méi)有區(qū)別，因此不影響。

然后我們輸入下面這組數(shù)據(jù)

4
7
3 8
8 1 0
2 7 4 4

當(dāng)輸入到

4

7

3

時(shí)，樹(shù)的結(jié)構(gòu)如下：

?

?接著輸入8之后，以下兩種情況，你覺(jué)得是哪一種？

?是下面的那種?？创a中下面這部分

在cin>>dp[1]的時(shí)候，已經(jīng)把dp[1]覆蓋成8了，因此公式變成了8+=max(8,0)，這樣一來(lái)答案就錯(cuò)了。不過(guò)到這一步，怎么改錯(cuò)也很明顯了，既然不想被覆蓋，那就引入一個(gè)變量來(lái)保存一下原本的dp[ j ]就行了嘛。

?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-597242.html

#include<iostream>
using namespace std;
int dp[1005] = { 0 };

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int r, j = 3, cnt = 2, MAX = -1, x = 0;
	cin >> r;
	cin >> dp[1];
	for (int i = 2; i <= r; ++i)
	{
		while (--j >= 1)
		{
			cin >> x;
			x += max(dp[j], dp[j - 1]);
			dp[j] = x;
		}
		++cnt;
		j = cnt + 1;
	}
	for (int i = 1; i <= r; ++i)
	{
		MAX = max(MAX, dp[i]);
	}
	cout << MAX;
	return 0;
}

于是空間成功從4MB多降到了800KB

當(dāng)然，還可以從下往上計(jì)算，最后的結(jié)果保存在dp[1][1]，這樣減少了最后遍歷整個(gè)數(shù)組的過(guò)程，但是輸入的時(shí)候沒(méi)法實(shí)現(xiàn)邊讀邊存，最終時(shí)間復(fù)雜度沒(méi)有差別。這里引用一下原題下方大神linlin1024的題解

?

到了這里，關(guān)于【洛谷】數(shù)字三角形（動(dòng)態(tài)規(guī)劃）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！