# 动态规划的解法， 每次考虑是否加入这个数字， 
# 行表示最大的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])

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];
}

#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;

}

这题显然是有 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;
}

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

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]);
    }
}

#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;
}

	#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;
    }
}

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();
    }
}

#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背包问题

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int m = in.nextInt();
        System.out.println(countOfsum(n, m, 1));
    }

    public static int countOfsum(int n, int m, int min) {
        if (m == 0)return 1;
        int count = 0;
        for (int i = min; i <= n && i <= m; i++) {
            count += countOfsum(n, m - i, i + 1);
        }
        return count;
    }
}

#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;
}

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]);
    }
}