本文共 1736 字，大约阅读时间需要 5 分钟。

数字和为sum的方法数

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

输入描述:

输出描述:

示例1

解析：

状态：dp[i][j]代表用前i个数字凑到j最多有多少种方案。

import java.util.Scanner;public class Main {       public static void main(String[] args) {           Scanner scanner = new Scanner(System.in);        int n = scanner.nextInt();// 数组长度为n表示n个数字        int sum = scanner.nextInt();// 部分元素求和sum        int[] value = new int[n+1];//初始化数组                for(int i=1;i<=n;i++){               value[i] = scanner.nextInt();        }        long[][] dp = new long[n+1][sum + 1];//动态规划数组        for(int j=0;j
   
    = value[i]) {                       dp[i][j] = dp[i-1][j]+ dp[i-1][j - value[i]];                }else if(j
   

简化版本：

import java.util.Scanner;public class Main {       public static void main(String[] args) {           Scanner scanner = new Scanner(System.in);        int n = scanner.nextInt();// 数组长度为n表示n个数字        int sum = scanner.nextInt();// 部分元素求和sum        int[] value = new int[n];//初始化数组        long[] dp = new long[sum + 1];//动态规划数组        dp[0] = 1;//index=0的初始化值        for (int i = 0; i < n; i++) {               value[i] = scanner.nextInt();            for (int j = sum; j >= 0; j--) {                   if (j >= value[i]) {                       dp[j] += dp[j - value[i]];                }            }        }        System.out.println(dp[sum]);    }}

来源：