跑步（C++，01背包方案数，DP）-创新互联
路人甲准备跑 n n n 圈来锻炼自己的身体，他准备分多次（ > 1 \gt1 >1）跑完，每次都跑正整数圈，然后休息下再继续跑。
为了有效地提高自己的体能，他决定每次跑的圈数都必须比上次跑的多。
可以假设他刚开始跑了 0 0 0 圈，那么请问他可以有多少种跑完这 n n n 圈的方案？
输入格式一行一个整数，代表 n n n。
输出格式一个整数表示跑完这 n n n 圈的方案数。
样例 #1 样例输入 #1212995645335对于 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）-创新互联
URL链接：http://hbruida.cn/article/dcgoop.html
