【牛客】数字和为sum的方法数（滴滴笔试）

快来打我* 2021-10-03 02:30 250阅读 0赞

链接：[https://www.nowcoder.com/questionTerminal/7f24eb7266ce4b0792ce8721d6259800][https_www.nowcoder.com_questionTerminal_7f24eb7266ce4b0792ce8721d6259800]  
来源：牛客网

\[编程题\]数字和为sum的方法数

给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。  
当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。

**输入描述:**

输入为两行:
     第一行为两个正整数n(1 ≤ n ≤ 1000)，sum(1 ≤ sum ≤ 1000)
     第二行为n个正整数A[i](32位整数)，以空格隔开。

**输出描述:**

输出所求的方案数

示例1

## 输入 ##

5 15 5 5 10 2 3

## 输出 ##

public class Main{
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int sum = sc.nextInt();
            int [] array = new int[n];
            for(int i = 0;i<n;i++){
                array[i] = sc.nextInt();
            }
    
            long [][]dp = new long[n+1][sum+1];//n个物品和为sum有多少方案。
            //表示当和为0是，就只有不取一种方案。
            for(int i = 0;i<=n;i++){
                dp[i][0] = 1;
            }
            //表示没有数字的时候就没有方案，但是这里要注意dp[0][0] = 1
            for(int i = 1;i<=sum;i++){
                dp[0][i] = 0;
            }
            for(int i = 1;i<=n;i++){
                for(int j = 0;j<=sum;j++){
                    if(array[i-1] <=j){
                        //表示这个数字放入多少种方案加上这个不放入有多少种方案
                        dp[i][j] = dp[i-1][j]+dp[i-1][j-array[i-1]];
                    }else {
                        dp[i][j] = dp[i-1][j];
                    }
                }
            }
            System.out.println(dp[n][sum]);
        }
    }

[https_www.nowcoder.com_questionTerminal_7f24eb7266ce4b0792ce8721d6259800]: https://www.nowcoder.com/questionTerminal/7f24eb7266ce4b0792ce8721d6259800