跑步(C++,01背包方案数,DP)-创新互联
路人甲准备跑 n n n 圈来锻炼自己的身体,他准备分多次( > 1 \gt1 >1)跑完,每次都跑正整数圈,然后休息下再继续跑。
成都创新互联公司服务项目包括马鞍山网站建设、马鞍山网站制作、马鞍山网页制作以及马鞍山网络营销策划等。多年来,我们专注于互联网行业,利用自身积累的技术优势、行业经验、深度合作伙伴关系等,向广大中小型企业、政府机构等提供互联网行业的解决方案,马鞍山网站推广取得了明显的社会效益与经济效益。目前,我们服务的客户以成都为中心已经辐射到马鞍山省份的部分城市,未来相信会继续扩大服务区域并继续获得客户的支持与信任!为了有效地提高自己的体能,他决定每次跑的圈数都必须比上次跑的多。
可以假设他刚开始跑了 0 0 0 圈,那么请问他可以有多少种跑完这 n n n 圈的方案?
输入格式一行一个整数,代表 n n n。
输出格式一个整数表示跑完这 n n n 圈的方案数。
样例 #1 样例输入 #1212
样例输出 #1995645335
提示
数据规模与约定对于 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://myzitong.com/article/dcgoop.html