2019-04-02 牛客网迅雷笔试题 整数求和

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

求和等于m的所有组合的个数。

示例1

输入

6 8

输出

4

经典0-1背包问题，即在一个可以装10kg的背包中，我们有1，2，2，3，4kg重的不同物品，在满足背包最大重量限制的前提下，背包中物品的总重量最大值是多少，。可以用回溯法把所有结果遍历，也可以用动态规划使用二维数组状态表去记录，0代表不放该物品，1代表放入该物品，对每个物品都这样，最后查询状态表最后一行的最远的1。空间换时间。

这题是变了一种问法，我们需要记录不同的组合，比如加起来等于3，3可以由1，2或0，3组成，我们把状态表的布尔值改成int去记录组成一个数的组合数就可以！看到这里明白的，可以去自己动手做一下先！

下面是代码

import java.util.Scanner;

/*
* 给定整数n，取若干个1到n的整数可求和等于整数m，
* 编程求出所有组合的个数。比如当n=6，m=8时，
* 有四种组合：
* [2,6], [3,5], [1,2,5], [1,3,4]。限定n和m小于120*/
public class Main {
    //假设有n个数，你可以用n个数里面 任意组合 合成一个m
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n =scanner.nextInt();
        int total = scanner.nextInt();
        int[][] status = new int[n+1][total+1];

        //1 , 2 , 3 , 4 凑 5
        //0  1
        //0  1  2  3
        //0  1  2  3  4  5（2+3凑了1个）  6
        //0  1  2  3  4  5 (2+3和1+4凑了2个) ... 这里的12345是j的下标，下标要记录的东西应该是凑出数据的组合数

        //我们要对status(状态表)进行处理，下面两个操作的意思是我们要操作的第一个元素是1。两种情况：可以放，也可以不放。
        //放了的话（1,1）的地方就是1种组合，值为1;不放的话(1,0)的地方就是1种组合，值为0
        //当我们操作第二个元素，我们首先要把上一个操作数的组合复制下来，再对这个被复制的地方加上当前操作数。
        //第一行：0 1
        //第二行：0 1 2 3 ->这里的2是0+2,3就是1+2，通过上一层的数相加本层操作数得出
        //对于这个二维矩阵
        //我们用行i当做当前的操作数，比如我从1开始遍历到第5个元素，我们现在要找到1-5的所有数组合，及i = 5，第五行操作的数就是5
        //用j当做相加后得出来的组合相加和的下标，比如1，2，3组合，1+3=4 ，我们可以在i=3,j=4的地方记录一下这里通过相加得出了4
        //可以看出我们没必要去管那些相加结果大于total的组合数
        status[1][0] = 1;

        status[1][1] = 1;

        for (int i = 2; i <= n; i++) {
            int posi = 0;
            for (int j = 0; j <= total; j++) {
                if (status[i-1][j] != 0)
                {
                    status[i][j] = status[i-1][j];
                    posi = j;
                }
            }
            //超过posi的数据就不要去加 否则会出现重复计算
            //我们只需要遍历到上一次最终j停止的地方就行
            //因为我们只需要在j之前的值加上当前操作数就可以得出新的组合了
            //i=1:0 1
            //i=2:0 1 2 3 这时候遍历到j=2，2的值是已经由0+2得出，再加变成2+2，使用了重复元素
            for (int j = 0; j <= posi; j++) {
                if (status[i][j]!=0&&j+i<=total)
                {
                    //这里有一点要注意的是，我们要的是总组合数，比如3可以有1，2组成也可以0，3组成
                    //我们如果在当前操作数累加得出某组合数新的组合方法，我们就累加i-1的j的值，得到新的组合数
                    //如
                    //i=1:1 1
                    //i=2:1 1 1 1
                    //i=3:1 1 1 2 1 1 这里的j=3得出2是因为首先是i-1的那层通过1，2得出3，我们这里又通过0+3的出3，我们累加多一个次就行
                   status[i][j+i] += status[i-1][j];
                }
            }
        }

        System.out.println(status[n][total]);
    }
}

测试通过

屏幕快照 2019-04-02 下午2.54.46.png