跑步（C++，01背包方案数，DP）-创新互联

题目描述

路人甲准备跑 n n n 圈来锻炼自己的身体，他准备分多次（ > 1 \gt1 >1）跑完，每次都跑正整数圈，然后休息下再继续跑。

成都创新互联公司服务项目包括马鞍山网站建设、马鞍山网站制作、马鞍山网页制作以及马鞍山网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，马鞍山网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到马鞍山省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！

为了有效地提高自己的体能，他决定每次跑的圈数都必须比上次跑的多。

可以假设他刚开始跑了 0 0 0 圈，那么请问他可以有多少种跑完这 n n n 圈的方案？

输入格式

一行一个整数，代表 n n n。

输出格式

一个整数表示跑完这 n n n 圈的方案数。

样例 #1 样例输入 #1

212

样例输出 #1

995645335

提示 数据规模与约定

对于 100 % 100\% 100% 的数据，保证 5 ≤ n ≤ 500 5\le n\le 500 5≤n≤500。

解题思路：

首先，这是一道01背包求方案数问题，接下来说明为什么

1）可以把要跑的圈数 n n n看作背包容量

2）可以把 1 1 1~ n n n圈看作 n n n个不同体积的物品

3）由于要跑的圈数必须一次多于一次，所以对于每个物品，只有选和不选两种情况

那么如何解决01背包求方案数问题呢？

我们先从**最简单的dfs**开始

int dfs(int w, int n) {//w为当前物品，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);//不选
}

思路是不是很简单？但是效率也很感人，所以我们需要进行优化

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

int mem[max_n + 1][max_n + 1] = {0};//记忆

int dfs(int w, int n) {//w为当前物品，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);//不选
}

当然，优化力度还是不够

注意到这个问题存在最优子结构，所以我们可以动态规划

for (int i = 0; i<= n; i++) mem[i][0] = 1;//初始化
for (int i = 1; i<= n; i++) {//i号物品
	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];
	}
}

现在时间上已经可以通过了，接下里进行空间优化

背包问题的空间优化自然少不了滚动数组

注意到j< i时，有mem[i][j] = mem[i - 1][j]，所以可以不修改直接合并为一行

注意到j >= i时，有mem[i][j] = mem[i - 1][j] + mem[i - 1][j - i]，即同列的上一行元素+同行左侧元素

故循环式可以修改为

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

至此，01背包求方案数问题解决了，AC代码如下

还有一件事，十年OI一场空，不开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;？记得回去看一眼题目哦）

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

文章题目：跑步（C++，01背包方案数，DP）-创新互联
文章起源：http://cqcxhl.cn/article/dcgoop.html