首页 > 试题广场 >

整数求和

[编程题]整数求和
  • 热度指数:3984 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
给定整数n,取若干个1到n的整数可求和等于整数m,编程求出所有组合的个数。比如当n=6,m=8时,有四种组合:[2,6], [3,5], [1,2,5], [1,3,4]。限定n和m小于120

输入描述:
整数n和m


输出描述:
求和等于m的所有组合的个数。
示例1

输入

6 8

输出

4
public class Main{
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        int m=scan.nextInt();
        System.out.println(getCount(n,m));
    }
    //0-1背包问题  f(n,m) 转化为两个子问题 f(n-1,m) 和 f(n-1,m-n)
    public static int getCount(int n, int m){
        if(m<1 || n<1) return 0;
        if(m<n) n=m;
        int sum=0;
        if(m==n) sum++;
        //不选中n
        sum+=getCount(n-1,m);
        //选中n
        sum+=getCount(n-1,m-n);
        return sum;
    }
}
编辑于 2018-09-07 16:06:14 回复(7)
#include<stdlib.h>
#include<stdio.h>

int cnt(int n,int m){
    if(m==0&&n>=0){
        return 1;
    }else if(n<0){
        return 0;
    }
    if(m>=n){
        return cnt(n-1,m-n)+cnt(n-1,m);
    }else{
        return cnt(n-1,m);
    }
}
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    printf("%d",cnt(n,m));
    return 0;
}

发表于 2018-09-12 14:34:19 回复(6)
其实就是背包问题的变体
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while((line = br.readLine()) != null) {
            String[] strArr = line.split(" ");
            int n = Integer.parseInt(strArr[0]), m = Integer.parseInt(strArr[1]);
            // 背包问题变体 dp[i][j]表示从1~i中组合成数字j的组合数
            int[][] dp = new int[n + 1][m + 1];
            for(int i = 0; i <= n; i++) dp[i][0] = 1;
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= m; j++){
                    if(i <= j)
                        dp[i][j] = dp[i - 1][j] + dp[i - 1][j - i];
                    else
                        dp[i][j] = dp[i - 1][j];
                }
            }
            System.out.println(dp[n][m]);
        }
    }
}


发表于 2020-11-10 21:55:24 回复(0)
a = input().strip().split()
n = int(a[0])
m = int(a[1])
resArr= [0 for x in range(m+1)]
for i in range(1,n+1):
    for j in range(m,0,-1):
        if i < j:
            resArr[j] = resArr[j]+resArr[j-i]
        elif i > j:
            resArr[j] = resArr[j]
        elif i == j:
            resArr[j] = resArr[j]+1
print(resArr[m])
发表于 2018-09-21 11:50:00 回复(0)

1

2

3

4

5

6

7

8

1

1

0

0

0

0

0

0

0

2

1

1

1

0

0

0

0

0

3

1

1

2

1

1

1

0

0

4

1

1

2

2

2

2

1

1

5

1

1

2

2

3

3

2

3

6

1

1

2

2

3

4

3

4








#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int N,M;
    cin>>N>>M;
    vector<vector <int>> dp(N+1,vector<int>(M+1,0));
    dp[1][0]=1;
    dp[1][1]=1;
    for(int i=2;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            if(j<i)
            {
                dp[i][j]=dp[i-1][j];
            }
            else if(j==i)
            {
                dp[i][j]=dp[i-1][j]+1;
            }
            else
            {
                dp[i][j]=dp[i-1][j]+dp[i-1][j-i];
            }
        }
    }
    //for(int i=0;i<dp[0].size();i++)
    //{
    //    cout<<dp[0][i]<<" ";
   // }
    //cout<<dp[3][3]<<endl;
    cout<<dp[N][M]<<endl;
    return 0;
}
发表于 2018-09-08 14:16:04 回复(3)
# 动态规划的解法, 每次考虑是否加入这个数字, 
# 行表示最大的n, 列表示sum,行和列均从0 开始
# 数组中的值为count,初始化数组时,第一列全为1, 表示sum为0时, 对所有的n结果均为1
n, m = list(map(int, input().strip().split()))
dp = [[1 if i == 0 else 0 for i in range(m+1)] for j in range(n+1)] for row in range(1, n+1):  for col in range(1, m+1):  if col - row < 0:
            dp[row][col] = dp [row-1][col]  else:
            dp[row][col] = dp[row - 1][col] + dp[row-1][col-row] print(dp[n][m])


发表于 2018-09-11 14:50:16 回复(0)

include <iostream>

using namespace std;
int main()
{
int n,m;
cin>>n>>m;
int f[121][121]={0};
for (int i=0;i<=n;i++)
{
f[i][0]=1;
}
for (int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(j>=i)
{
f[i][j]=f[i-1][j-i]+f[i-1][j];
}
else
{
f[i][j]=f[i-1][j];
}
}
}
cout<<f[n][m];
}

编辑于 2018-09-06 19:42:29 回复(0)
#include<iostream>
#include<vector>
using namespace std;

int n,m,x;
void  backing(int start,int sum){
    if(sum==m){
        ++x;
        return;
    }
    for(int i=start;i<=n && sum+i<=m;i++){
        sum+=i;
        backing(i+1,sum);
        sum-=i;
    }
}

int main()
{
    cin>>n>>m;
    backing(1,0);
    cout<<x;

}


发表于 2021-09-27 15:03:25 回复(1)

这题显然是有 dp 做法的,但是一看数据范围这么小,果断搜索了。

/**
 *  Author: yurzhang
 *  Date: 2020/04/22
 *
 *  Natsuiro Matsuri
 */
%:pragma GCC optimize("Ofast,inline,unroll-loops")
#include <cstdio>

int n,m,ans;

int now;
void dfs(int last) {
    for(int i=last+1;i<=n;++i) {
        if(now+i==m) ++ans;
        if(now+i>=m) break;
        now+=i; dfs(i); now-=i;
    }
}

int main() {
    scanf("%d%d",&n,&m);
    dfs(0);
    printf("%d",ans);
    return 0;
}

顺便,题目描述最好说清楚不能选重复的数,虽然看样例可以得知这个信息。

发表于 2020-04-22 23:49:33 回复(0)
import java.util.*;

public class Main {
    private static final int MAX = 125;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[]dp = new int[MAX];
        dp[0] = 1;
        for (int i=1; i<=n; i++) {
            for (int j=m; j>=i; j--) {
                dp[j] += dp[j - i];
            }
        }
        System.out.println(dp[m]);
    }
}
发表于 2019-02-24 20:41:18 回复(0)
#include <iostream>
using namespace std;
int Count(int n,int m)
{
    if(!n)
    {
        if (!m)
            return 1;
        else 
            return 0;
    }
    if(n>m)
        return Count(m,m);
    else
        return Count(n-1,m)+Count(n-1,m-n);
     
}
int main()
{
    int n,m;
    cin>>n>>m;
    cout<<Count(n,m);
    return 0;
}

发表于 2018-10-01 14:41:40 回复(0)
#include <iostream> #include<vector> using namespace std; int res=0; void solve(int n, int m, vector<int>& s, int num) {     if (m == 0)  res++;     for (int i = num; i <= n&&i <= m; i++) {         s.push_back(i);         solve(n, m - i, s, i + 1);         s.pop_back();     } } int main() {     int n, m;     while (cin >> n >> m) {         vector<int> s;         solve(n, m, s, 1);         cout<<res<<endl;         res=0;     } }
编辑于 2018-09-27 12:40:20 回复(0)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class NumberSum {
    public static void main(String[] args) {

        Scanner in = new Scanner(
                new BufferedReader(new InputStreamReader(System.in)));
        while (in.hasNext()) {
            int n = in.nextInt();
            int sum = in.nextInt();
            int[] a = new int[n];
            for (int i = 1; i <= n; i++) {
                a[i - 1] = i;
            }
            long[] dp = new long[sum + 1];
            dp[0] = 1;
            //只能选择一次,所以01背包,从大到小
            for (int i = 0; i < n; i++) {
                for (int j = sum; j >= a[i]; j--) {
                    dp[j] += dp[j - a[i]];
                }
            }
            System.out.println(dp[sum]);
        }
        in.close();
    }
}
发表于 2018-09-12 16:47:27 回复(0)
我觉得题目有问题
发表于 2018-09-25 20:03:23 回复(1)
由于组合个数与n、m的取值存在规律,故可以根据规律,即根据各种n、m取值之间的关系,可以推导当前n、m取值对应的组合个数。此回答,参考了几个前面的答案。

表内单元格a[n][m]表示:从1~n中挑选几个数的和等于m,存在的组合个数
当n >= m时,图中蓝色部分(深蓝+淡蓝)
1~m-1,可以成为组合的加数,即用1到m-1表示m,=> a[m-1][m]
m, 可以成为组合的加数,即刚好单个加数{m}表示m, => 1
m+1~n, 由于这些数都大于m,不可能成为加数 => 0
a[n][m] = a[m-1][m] + 1

当n < m时,图中橙色部分
加数中无n,从1~n-1中挑选几个数的和等于m => a[n-1][m]
加数中有n,从1~n-1中挑选几个数的和加上n等于m,相当于,从1~n-1中挑选几个数的和等于 m-n => a[n-1][m-n]
把这两块加起来就是结果集了
a[n][m] = a[n-1][m] + a[n-1][m-n]



发表于 2018-09-13 21:58:55 回复(6)
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    vector<int> dp(m+1,0);
    dp[0]=1;
    for(int i=1;i<=n;i++) //注意是1到n
    {
        for(int j=m;j>=i;j--)
        {
            dp[j]=dp[j]+dp[j-i];
        }
    }
    cout<<dp[m]<<endl;
}
//0-1背包问题

发表于 2018-09-10 15:47:29 回复(3)
#include <stdio.h>

int main(int argc, const char * argv[]){
    int a[120][120];
    int n, m;
    scanf("%d %d", &n, &m);
    
    // 初始化
    for(int i=1; i<=n; i++){
        a[i][0] = 0;
        a[0][i] = 0;
        a[i][1] = 1;
        if(i==1){
            a[1][i] = 1;
        }else{
            a[1][i] = 0;
        }
    }
    
    // 进行计算
    for(int i=2; i<=n; i++){
        for(int j=2; j<=m; j++){
            if(i>=j){
                // [1,j,i]
                // 分解 [j-1, j] + [j][j] + [j+1][j]
                // 1~j-1,可以成为组合的加数,即用1到j-1表示j,=> a[j-1][j]
                // j, 可以成为组合的加数,即刚好单个加数{j}表示j, => 1
                // j+1~j, 由于这些数都大于j,不可能成为加数 => 0
                a[i][j] = a[j-1][j] + 1;
            }else{
                // [1,i,j]
                // 分解 [i-1][j] + [i-1][j-i]
                // 加数中无i,从1~i-1中挑选几个数的和等于j => a[i-1][j]
                // 加数中有i,从1~i-1中挑选几个数的和加上i等于j,相当于,从1~i-1中挑选几个数的和等于 j-i => a[i-1][j-i]
                a[i][j] = a[i-1][j] + a[i-1][j-i];
            }
        }
    }
    printf("%d", a[n][m]);
    return 0;
}

发表于 2023-03-27 22:24:25 回复(0)
import java.util.Scanner;

public class Main {
    // 整数求和的组合
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        fun(n, m);
    }
    // 动态规划-01背包-状态压缩
    // dp[j] 前i个数字凑出j的可能方案数
    // base case:dp[0] = 1
    // 方程 dp[i] = dp[i] + dp[j-i]
    // 计算顺序 一维逆序计算
    public static void fun(int n, int m) {
        int[] dp = new int[m+1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= i; j--) {
                dp[j] += dp[j-i];
            }
        }
        System.out.println(dp[m]);
    }
}
发表于 2022-07-14 21:43:40 回复(0)
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    vector<int>dp(m);
    dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=i;j--)
        {
            dp[j]+=dp[j-i];
        }
    }
    cout<<dp[m];
    return 0;
     
}

发表于 2020-07-14 17:59:48 回复(0)
//规模不大,递归感觉就可以,空间占用更少
//如果规模大,可以把dp[n][m]都用额外空间存储,避免重复计算
#include<iostream>
using namespace std;

int fun(int n, int m) {
    if(m == 0) {
        return 0;
    }
    else if(n>=m) {
        return fun(m-1,m) + 1;
    }
    else if((1+n)*n/2 < m) {
        return 0;
    }
    else {
        return fun(n-1, m) + fun(n-1, m-n);
    }
}

int main() {
    int n,m;
    cin>>n>>m;
    cout<<fun(n,m)<<endl;
    return 0;
}

发表于 2020-07-04 11:24:19 回复(0)