迅雷2018校园招聘-数字组合问题

题目

给定整数n，取若干个1到n的整数可求和等于整数m，编程求出所有组合的个数。比如当n=6，m=8时，有四种组合：[2,6], [3,5], [1,2,5], [1,3,4]。限定n和m小于120

思路

首先，这道题想要通过暴力搜索是无法实现的，那么只能找规律。
根据题意找规律，构建如图所示的表。要求 f ( n , m ) f(n,m) f(n,m)的值
首先处理边界问题：第一行也就是 f ( 1 , 1 ) = 1 f(1,1)=1 f(1,1)=1,其他 f ( 1 , m ) = 0 f(1,m)=0 f(1,m)=0;
第一列， f ( n , 1 ) = 1 f(n,1)=1 f(n,1)=1;

分三种情况来讨论：（横纵坐标分别用 i , j i,j i,j表示）

第一种，当 i i i= j j j时， 首先最直接的就是直接取 i i i就是一种组合方式，而除此之外 i i i不存在其他组合情况能够使得和为 j j j。因此，我们不妨把 i i i舍去，退一步，我们关心 f ( i − 1 , j ) f(i-1,j) f(i−1,j)的值，只要在这个值的基础上加上一就是 f ( i , j ) f(i,j) f(i,j)的值了。因此，当 i i i= j j j时， f ( i , j ) = f ( i − 1 , j ) + 1 f(i,j)=f(i-1,j)+1 f(i,j)=f(i−1,j)+1；
第二种，当 i i i> j j j时，这种情况也很简单，由于 i i i大于 j j j的部分都不能贡献组合次数，有和没有都是一样的，因此 f ( i , j ) = f ( i − 1 , j ) f(i,j)=f(i-1,j) f(i,j)=f(i−1,j)；
第三种，当 i i i< j j j时，这是稍微复杂一点。这时 i i i的引入是会在 f ( i − 1 , j ) f(i-1,j) f(i−1,j)的基础上改变组合次数的。至于到底会引入多少个次数，其实就是确定前面的 i − 1 i-1 i−1个数能够有多少中可能可以组合成 j − i j-i j−i。因此这一步的递推 f ( i , j ) = f ( i − 1 , j ) + f ( i − 1 , j − i ) f(i,j)=f(i-1,j)+f(i-1,j-i) f(i,j)=f(i−1,j)+f(i−1,j−i)；

（图来源于牛客网）

代码实现

#include"bits/stdc++.h"
using namespace std;
 
int main()
{
    int n,m;
    cin>>n>>m;
    vector<vector<int>> seq(n+1, vector<int>(m+1,0));
    for(int i=1;i<n+1;i++)
        seq[i][1]=1;
    for(int i=2;i<n+1;i++)
    {
        for(int j=2;j<m+1;j++)
        {
            if(i==j)
                seq[i][j]=1+seq[i-1][j];
            else if(i<j)
                seq[i][j]=seq[i-1][j-i]+seq[i-1][j];
            else
                seq[i][j] = seq[i-1][j];
        }
    }
    cout<<seq[n][m];
    return 0;
}

上述代码可以进一步优化，不必要求出所有的位置的值，可以使用方向递推的方式，只计算需要的位置即可。