題目描述

路人甲準(zhǔn)備跑 n n n 圈來鍛煉自己的身體，他準(zhǔn)備分多次（ > 1 \gt1 >1）跑完，每次都跑正整數(shù)圈，然后休息下再繼續(xù)跑。

成都創(chuàng)新互聯(lián)公司服務(wù)項(xiàng)目包括馬鞍山網(wǎng)站建設(shè)、馬鞍山網(wǎng)站制作、馬鞍山網(wǎng)頁制作以及馬鞍山網(wǎng)絡(luò)營(yíng)銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢(shì)、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，馬鞍山網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到馬鞍山省份的部分城市，未來相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

為了有效地提高自己的體能，他決定每次跑的圈數(shù)都必須比上次跑的多。

可以假設(shè)他剛開始跑了 0 0 0 圈，那么請(qǐng)問他可以有多少種跑完這 n n n 圈的方案？

輸入格式

一行一個(gè)整數(shù)，代表 n n n。

輸出格式

一個(gè)整數(shù)表示跑完這 n n n 圈的方案數(shù)。

樣例 #1 樣例輸入 #1

212

樣例輸出 #1

995645335

提示 數(shù)據(jù)規(guī)模與約定

對(duì)于 100 % 100\% 100% 的數(shù)據(jù)，保證 5 ≤ n ≤ 500 5\le n\le 500 5≤n≤500。

解題思路：

首先，這是一道01背包求方案數(shù)問題，接下來說明為什么

1）可以把要跑的圈數(shù) n n n看作背包容量

2）可以把 1 1 1~ n n n圈看作 n n n個(gè)不同體積的物品

3）由于要跑的圈數(shù)必須一次多于一次，所以對(duì)于每個(gè)物品，只有選和不選兩種情況

那么如何解決01背包求方案數(shù)問題呢？

我們先從**最簡(jiǎn)單的dfs**開始

int dfs(int w, int n) {//w為當(dāng)前物品，n為背包容量
	if (n == 0) return 1;//找到方案
	if (w == 0) return 0;//未找到

	if (n >= w) return dfs(w - 1, n - w) + dfs(w - 1, n);//選 + 不選
	else return dfs(w - 1, n);//不選
}

思路是不是很簡(jiǎn)單？但是效率也很感人，所以我們需要進(jìn)行優(yōu)化

最容易想到的就是記憶了：w和n一定，dfs(w, n)一定

int mem[max_n + 1][max_n + 1] = {0};//記憶

int dfs(int w, int n) {//w為當(dāng)前物品，n為背包容量
	if (n == 0) return 1;//找到方案
	if (w == 0) return 0;//未找到

	if (mem[w][n]) return mem[w][n];//記憶
	if (n >= w) return mem[w][n] = (dfs(w - 1, n - w) + dfs(w - 1, n));//選 + 不選
	else return mem[w][n] = dfs(w - 1, n);//不選
}

當(dāng)然，優(yōu)化力度還是不夠

注意到這個(gè)問題存在最優(yōu)子結(jié)構(gòu)，所以我們可以動(dòng)態(tài)規(guī)劃

for (int i = 0; i<= n; i++) mem[i][0] = 1;//初始化
for (int i = 1; i<= n; i++) {//i號(hào)物品
	for (int j = 1; j<= n; j++) {//j背包容量
		if (j >= i) mem[i][j] = mem[i - 1][j] + mem[i - 1][j - i];
		else mem[i][j] = mem[i - 1][j];
	}
}

現(xiàn)在時(shí)間上已經(jīng)可以通過了，接下里進(jìn)行空間優(yōu)化

背包問題的空間優(yōu)化自然少不了滾動(dòng)數(shù)組

注意到j< i時(shí)，有mem[i][j] = mem[i - 1][j]，所以可以不修改直接合并為一行

注意到j >= i時(shí)，有mem[i][j] = mem[i - 1][j] + mem[i - 1][j - i]，即同列的上一行元素+同行左側(cè)元素

故循環(huán)式可以修改為

for (int i = 1; i<= n; i++)
	for (int j = n; j >= i j--)
		mem[j] += mem[j - i];

至此，01背包求方案數(shù)問題解決了，AC代碼如下

還有一件事，十年OI一場(chǎng)空，不開long long見祖宗，記得要防止溢出qwq

#includeusing namespace std;
const int max_n = 500;

long long mem[max_n + 1] = {0 };//記憶

int main() {mem[0] = 1;//初始化
	int n;
	cin >>n;
	for (int i = 1; i<= n; i++)
		for (int j = n; j >= i; j--)
			mem[j] += mem[j - i];
	cout<< mem[n] - 1;
	return 0;
}

（為什么要cout<< mem[n] - 1;？記得回去看一眼題目哦）

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

分享題目：跑步（C++，01背包方案數(shù)，DP）-創(chuàng)新互聯(lián)
文章來源：http://jinyejixie.com/article8/dcgoop.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供Google、云服務(wù)器、手機(jī)網(wǎng)站建設(shè)、標(biāo)簽優(yōu)化、定制開發(fā)、用戶體驗(yàn)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)