zjh

用户名：speaksoftly

访问量：24718

签　名：

搞spring去了...不能愉快的刷题了...

等　　级
排　　名	172
经　　验	6955
参赛次数	10
文章发表	37
年　　龄	0
在职情况	学生
学　　校	海南
专　　业

　　自我简介：

TA的其他文章

信息学奥赛一本通T1242-网线主管（C++代码）二分
浏览：1468

你可能喜欢

C语言程序设计教程（第三版）课后习题7.2 （Java代码）

蓝桥杯算法提高VIP-数的划分-题解(C++代码)蒟蒻的me也来写一写题解

　　作者: zjh　　　　发表时间：2019-06-28 14:10:25 浏览：949　|　评论：0　

原题链接：蓝桥杯算法提高VIP-数的划分

思路：
	求n的划分方案数，我们看样例
	3 可以划分成
	1，1，1
	1，2
	3
	不难看出只要 <= n的情况下一个数可以无限使用
	那么同样的，面对一个数n，他可以取0 ~ n这些数，而面对一个数，我们可以选择取或不取，如果我们取了这个数 i，那么我们之后取的数就不能超过 n - i，如果我们不取这个数，则可选的数还是0 ~ n
	那么我们取了 i 这个数，那我们只需要加上n - i的方案数就是当前n的方案数
	
	子问题:
	我们想要知道n的方案数就必须要知道n - i的方案数
	而n - i的方案数是多少呢？
	同样的面对n - i可以取0 ~ (n - i)个数......
	......
	......
	最后n = 0的时候 他只能取一个数0，方案数是1
	
	初始化:
	只能选择0这个数来组合n，0这个数组合0的方案数是1，0组合 1～n 的方案数是0
	dp[0][0] = 1;
	j > 0    dp[0][j] = 0;
	
	转移方程:
	dp[i][j] = dp[i - 1][j] + dp[i][j - i];
		i 代表当前这个数字是否要选，j 代表组组成 j 这个数方案
		条件:
			i == 0 && j == 0    dp[i][j] = 1
			i == 0 && j > 0      dp[i][j] = 0;
			i > 0 && j >= i       dp[i][j] = dp[i - 1][j] + dp[i][j - i];
			
	时间复杂度:O(n^2), 空间复杂度O(n^2) 可优化为O(n)
	
	答案:
		dp[n][n];	//组成n这个数且0～n这些数都经过选取or不选取的方案数
	
	code:
	
    #include "stdio.h"
    #include "iostream"
    using namespace std;
    int main() {
        int n;
        scanf("%d", &n);
        int dp[n + 1][n + 1];
		//i：当前i这个数是否放入j的组合方案中
        for(int i = 0; i <= n; i++){
			//j：当前j这个数的组合方案
            for(int j = 0; j <= n; j++){
                if(i == 0){	//初始化
                    if(j == 0){
                        dp[i][j] = 1;
                    }else{
                        dp[i][j] = 0;
                    }
                    continue;
                }
                dp[i][j] = dp[i - 1][j];	//把上一次i产生的值带到当前i这个地方，枚举方案数
                if(j >= i){
                    dp[i][j] += dp[i][j - i];
                }
            }
        }
        cout << dp[n][n] << endl;
        return 0;
    }
	
	
	
	
	空间复杂度为O(n)的优化code:

#include "stdio.h"
    #include "iostream"
    using namespace std;
    int main() {
        int n;
        scanf("%d", &n);
        int dp[n + 1];	//这里把i去掉，我们发现转移方程依赖的是i - 1，所以我们可以用滚动数组从而把数组变成[2][n + 1]的大小，而我们发现，当需要用到j - i时，实际上我们用的是dp[i][j - i]当前这一次已经改变过的状态，所以我们甚至可以不需要用滚动数组
        for(int i = 0; i <= n; i++){
            for(int j = 0; j <= n; j++){
                if(i == 0) {
                    if (j == 0) {
                        dp[j] = 1;
                    } else {
                        dp[j] = 0;
                    }
                    continue;
                }
    			//去掉转存dp[i][j] = dp[i - 1][j]，因为此时的dp[j] == dp[i - 1][j]
                if(j >= i){
                    dp[j] += dp[j - i];
                }
            }
        }
        cout << dp[n] << endl;
        return 0;
    }
	
	
	
	
	
	
	
	实际上这道题就是一道完全背包，i 实际上就是物品重量，j是背包容量
	区别是把物品价值换成了方案数

0.0分

5 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

zjh

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

整人!!

十->二进制转换（C++代码）（零和负数需要特殊处理）

C语言程序设计教程（第三版）课后习题7.2 （Java代码）

简单的a+b （C语言代码）

蓝桥杯算法提高VIP-数的划分-题解(C++代码)蒟蒻的me也来写一写题解

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

勾股数（C语言代码）

杨辉三角（C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

zjh

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

整人!!

十->二进制转换 （C++代码）（零和负数需要特殊处理）

C语言程序设计教程（第三版）课后习题7.2 （Java代码）

简单的a+b （C语言代码）

蓝桥杯算法提高VIP-数的划分-题解(C++代码)蒟蒻的me也来写一写题解

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

勾股数 （C语言代码）

杨辉三角 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

十->二进制转换（C++代码）（零和负数需要特殊处理）

　　评论区

勾股数（C语言代码）

杨辉三角（C语言代码）