精华内容
下载资源
问答
  • 整数拆分 Jack Cheng学完了计算机基础导论,了解到任何一个数都可以用二进制数来表示,爱玩游戏的他忍不住想要玩一个游戏,既然可以用二进制数表示,那么就可以写成若干个二进制数相加,例如: 7=1+2+4 7=1+2+2+2 7=...

    整数拆分

    Jack Cheng学完了计算机基础导论,了解到任何一个数都可以用二进制数来表示,爱玩游戏的他忍不住想要玩一个游戏,既然可以用二进制数表示,那么就可以写成若干个二进制数相加,例如: 7=1+2+4 7=1+2+2+2 7=1+1+1+4 7=1+1+1+2+2、7=1+1+1+1+1+2 ,7=1+1+1+1+1+1+1 总共有六种不同的拆分方式。 再比如:4可以拆分成:4 = 4,4 = 1 + 1 + 1 + 1,4 = 2 + 2,4=1+1+2。 用f(n)表示n的不同拆分的种数,例如f(7)=6. 要求编写程序,读入n(不超过1000000),输出f(n)%1000000000。现在他希望你和他一起来玩这个游戏。

    输入格式:

    请在这里写输入格式。例如:输入在一行中给出2个绝对值不超过1000的整数A和B。

    输出格式:

    第一行输入n表示有那个输入,后面每一行输入一个N(1<=N<=1000000)。所有输出只占一行(行末无多余空格)。

    输入样例:

    1
    7
    

    输出样例:

    6
    
    思路

    如果这个数n是奇数,那么f(n)=f(n-1),相当于只是多加了“1”,并没有改变其他1与1的组合;
    如果这个数是偶数,那么f(n)=f(n-1)+f(n/2):比如6=5+1或3+3,6的分法就等于5的分法加上3的分法(加一个3的分法,因为3和3分法相同,加两遍会重复:1+2+1+2…)

    C++代码
    #include<stdio.h>
    #include<iostream>
    #include<stdlib.h>
    #include <string>
    using namespace std;
    
    int nums=1000000;
    long long int result[1000000];
    void way(){
        for(int n=1;n<=nums;n++){
            if(n==1) result[n]=1;
    	    else if(n%2==0) result[n]=result[n-1]+result[n/2];
    	    else if(n%2==1) result[n]=result[n-1];
        }
    }
    int main(){
    	int N,num[10000];
    	cin>>N;
        way();
        for(int i=0;i<N;i++){
    		cin>>num[i];
    	}
        cout<<result[num[0]];
        for(int i=1;i<N;i++){
            cout<<" "<<result[num[i]];
        }
        return 0;
    }
    
    展开全文
  • 把5拆分成若干无序正整数的和(若干可以包含1),请问有多少种拆分方法? 直接用枚举法实现: 5 = 5 5 = 4+1 5 = 3+2 5 = 3+1+1 5 = 2+2+1 5 = 2+1+1+1 5 = 1+1+1+1+1 很显然,结果为7。注意这里5 = 4+1和5=1+4是...
  • //采用动态规划求解整数拆分问题。 //设f(n,k)为n的k拆分的拆分方案个数: //其中,n表示被划分的数,k表示被划分出来的数中的可能出现的最大值, // f(n,k)的值表示划分的方法个数 //(1)当n = 1或者k = 1时,...
    #include<stdio.h>
    #define MAXN 10
    //采用动态规划求解整数拆分问题。
    //设f(n,k)为n的k拆分的拆分方案个数:
    //其中,n表示被划分的数,k表示被划分出来的数中的可能出现的最大值,
    //                       f(n,k)的值表示划分的方法个数
    //(1)当n = 1或者k = 1时,显然f(n,k) = 1。
    //(2)当n<k时,有f(n,k) = f(n,n)。
    //(3)当n = k时,
    //		其拆分方案有将正整数n无序拆分成最大数为n - 1的拆分方案,
    //		以及将n拆分成1个n(n = n)的拆分方案,后者仅仅一种,
    //		所以有f(n,n) = f(n,n - 1) + 1。
    //(4)当n>k时,根据拆分方案中是否包含k,可以分为两种情况:
    //	① 拆分中包含k的情况:即一部分为单个k,
    //		另外一部分为{ x1,x2,…,xi },后者的和为n - k,
    //		后者中可能再次出现k,因此是(n - k)的k拆分,
    //		所以这种拆分方案个数为f(n - k,k)。
    //	② 拆分中不包含k的情况:
    //		则拆分中所有拆分数都比k小,即n的(k - 1)拆分,
    //		拆分方案个数为f(n,k - 1)。
    
    int dp[MAXN][MAXN];			//动态规划数组
    //划分方法
    //	f(n,k) = 1							当n = 1或者k = 1
    //	f(n,k) = f(n,n)					当n < k
    //	f(n,k) = f(n,n - 1) + 1			当n = k
    //	f(n,k) = f(n - k,k) + f(n,k - 1)	当n < k
    
    void Split(int n, int k)		//求解算法
    {
    	for (int i = 1; i <= n; i++)
    		for (int j = 1; j <= k; j++)
    		{
    			if (i == 1 || j == 1)
    				dp[i][j] = 1;
    			else if (i < j)
    				dp[i][j] = dp[i][i];
    			else if (i == j)
    				dp[i][j] = dp[i][j - 1] + 1;
    			else
    				dp[i][j] = dp[i][j - 1] + dp[i - j][j];
    		}
    }
    int fun(int n, int k)			//求解算法
    {
    	if (n == 1 || k == 1)
    		return 1;
    	else if (n < k)
    		return fun(n, n);
    	else if (n == k)
    		return fun(n, n - 1) + 1;
    	else
    		return fun(n - k, k) + fun(n, k - 1);
    }
    
    int dp_2[MAXN][MAXN];
    int dpf(int n, int k)			//求解算法
    {
    	if (dp_2[n][k] != 0)
    		return dp_2[n][k];
    	if (n == 1 || k == 1)
    	{
    		dp_2[n][k] = 1;
    		return dp_2[n][k];
    	}
    	else if (n < k)
    	{
    		dp_2[n][k] = dpf(n, n);
    		return dp_2[n][k];
    	}
    	else if (n == k)
    	{
    		dp_2[n][k] = dpf(n, k - 1) + 1;
    		return dp_2[n][k];
    	}
    	else
    	{
    		dp_2[n][k] = dpf(n, k - 1) + dpf(n - k, k);
    		return dp_2[n][k];
    	}
    }
    
    int main()
    {
    	int i, j;
    	int n = 5, k = 5;//n表示被划分的数,k表示被划分出来的数中的最大值
    	printf("\n动态规划法求解:\n");
    	Split(n, k);
    	for (i = 1; i <= n; i++)
    	{
    		for (j = 1; j <= k; j++)
    		{
    			printf("%3d", dp[i][j]); 
    			//dp[i][j]=x表示将i划分,且划分的数的最大值可以为j,共有x种划分方法
    		}
    		printf("\n");
    	}
    	printf("\n递归法求解:\n");
    	printf("%3d", fun(n, k));
    
    	printf("\n备忘录法求解:\n");
    	dpf(n, k);
    	for (i = 1; i <= n; i++)
    	{
    		for (j = 1; j <= k; j++)
    		{
    			printf("%3d", dp_2[i][j]);
    			//dp_2[i][j]=x表示将i划分,且划分的数的最大值可以为j,共有x种划分方法
    		}
    		printf("\n");
    	}
    	return  0;
    }
    
    
    展开全文
  • 动态规划整数拆分

    2021-05-23 21:22:50
    给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2: 输入: 10 输出: 36 解释: 10 = 3 + 3 +...

    给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

    示例 1:
    输入: 2
    输出: 1
    解释: 2 = 1 + 1, 1 × 1 = 1。
    示例 2:
    输入: 10
    输出: 36
    解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
    代码:

     public int integerBreak(int n) 
     {
           int[] dp=new int[n+1];
        	for(int i=2;i<=n;i++)
        	{
        		int min=0;
        		for(int j=1;j<i;j++)
        		{
        			min=Math.max(min, Math.max(j*(i-j), j*dp[i-j]));
        		}
        		dp[i]=min;
        	}
        	return dp[n];
     }
    
    展开全文
  • 整数拆分 给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2: 输入: 10 输出: 36 解释: ...

    LeetCode 343. 整数拆分

    给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
    示例 1:

    输入: 2
    输出: 1
    解释: 2 = 1 + 1, 1 × 1 = 1。
    

    示例 2:

    输入: 10
    输出: 36
    解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
    

    数学法:
    尽可能多的拆成3
    如果能整除3:乘积为3^(n//3)
    如果除3的余数为1:拆成(n//3-1)个3和两个2,因为13 < 22
    如果除3的余数为2:拆成(n//3)个3和一个2

    class Solution:
        def integerBreak(self, n: int) -> int:
            if n <= 3:
                return n - 1
            a = n // 3
            b = n % 3
            if b == 0:
                return 3 ** a
            if b == 1:
                return 3 ** (a-1) * 4
            if b == 2:
                return 3 ** a * 2
    

    动态规划
    dp[i]表示整数i对应的最大乘积,那么dp[i]的值应是dp[j]*(i-j),j属于[1,i]的最大值,同时注意dp[i]对应的值是经过拆分了的,所以还应判断两个数拆分的情况,即j*(i-j)的值,取最大即可。
    也即一个数可以拆成两个数,或者拆完之后继续拆分

    class Solution:
        def integerBreak(self, n: int) -> int:
            if n <= 3:
                return n - 1
            dp = [0] * (n+1)
            dp[1] = 1
            for i in range(2, n+1):
                for j in range(1, i):
                    dp[i] = max(dp[i], dp[j] * (i-j))
                    dp[i] = max(dp[i], j * (i-j))
            return dp[n]
    
    展开全文
  • 动态规划求解整数拆分问题 一、问题描述: 写f(6,4)的求解过程,实际是在求dp[5][5]。 二、问题分析 详情可见博客https://blog.csdn.net/weixin_44279771/article/details/105877374 ????传送门 二、正确答案
  • 动态规划整数拆分

    千次阅读 2019-05-17 13:59:09
    时间限制:1秒空间限制:65536K热度指数:8566 ...一个整数总可以拆分为2的幂的和,例如: 7=1+2+4 7=1+2+2+2 7=1+1+1+4 7=1+1+1+2+2 7=1+1+1+1+1+2 7=1+1+1+1+1+1+1 总共有六种不同的拆分方式。 再...
  • 问题描述 求将正整数n无序拆分成最大数为k(称为n的k拆分)的拆分...采用动态规划求解整数拆分问题。设f(n,k)为n的k拆分的拆分方案个数: 因此,f(n,k) = f(n-k,k) + f(n,k-1) 状态转移方程: 代码 int d...
  • 这也相当于是整数拆分问题,即把一个整数n拆分为m个数的和。 思路:起初想着能不能用概率论中的知识直接计算,后面发现算不了,只能通过递推公式以及动态规划计算。 设S(n,m)是n个物体分成m堆的方法数,则有递推公式...
  • (力扣---动态规划)整数拆分

    千次阅读 2019-03-15 01:10:29
    (力扣—动态规划)整数拆分 问题描述 给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2: ...
  • dp[i]代表i这个数拆分后所能得到的最大乘积 class Solution { public: int integerBreak(int n) { vector<int> dp(n+1,0); dp[1]=1; for(int i=2;i<=n;i++) for(int j=1;j<i;j++) dp[i]=max(dp[i...
  • 1. 解题思路 #include <bits/stdc++.h> #define MAXN 500 int dp[MAXN][MAXN]; using namespace std; void Split(int p, int q) { for (int n = 1; n <= p; n++) ... k++...
  • 问题描述 思路 注意事项 此题的有一个坑,,,首先明白函数的定义是:将i分割,获得的最大乘积 但是我们在计算的时候需要考虑不分割的情况,即直接用j*(i-j) 代码 class Solution { private: ...
  • 动态规划-整数拆分/完全背包方案数

    千次阅读 2019-01-22 14:36:29
    一个整数总可以拆分为2的幂的和,例如: 7=1+2+4 7=1+2+2+2 7=1+1+1+4 7=1+1+1+2+2 7=1+1+1+1+1+2 7=1+1+1+1+1+1+1 总共有六种不同的拆分方式。 再比如:4可以拆分成:4 = 4,4 = 1 + 1 + 1 + 1,4 = 2 + 2,4=1+1+2...
  • 给定一个正整数n,将其拆分为至少两个正整数的和,并使...拿到题目一看,肯定是动态规划的思想。分为两种情况:将i拆成j和i-j。将j固定,然后分类讨论(i-j);如果i-j是不可再分的:dp[i] = j*(i-j),如果(i-j)还...
  • 给定一个正整数n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例2: 输入: 10 输出: 36 ...
  • 整数拆分基本思想1:动态规划 题目:343. 整数拆分 给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 =...
  • [动态规划]整数拆分(纯DP)

    千次阅读 2015-09-29 15:58:14
    Name:整数拆分 两种做法 (dp) Actor:HT Time:2015年9月28日 Error Reporte: 1.初始化边界处理 没弄清 */ #include #include #include #include #include #include using namespace std; #define N...
  • 第一种方法 是采用自上而下得递归方案,所以采用了递归,时间开销比较大,所以在领扣中时间超时了 int max(int a, int b) { return a>=b?a:b; } int max3(int a,int b,int c) ... return(max(a,max(b,c)));...

空空如也

空空如也

1 2 3 4 5 ... 19
收藏数 364
精华内容 145
关键字:

动态规划整数拆分