数字和为sum的方法数

import java.util.Arrays;
import java.util.Scanner;

public class GetTheSum {
    public static void main(String[] args) {
        //testIt();
        Scanner scanner = new Scanner(System.in);
        int i = 0;
        String[] lines = new String[2];
        while (i <= 1 && scanner.hasNextLine()) {
            lines[i] = scanner.nextLine();
            i++;
        }

        String[] nAndSum = lines[0].split("\\s+");
        int n = Integer.parseInt(nAndSum[0]);
        int sum = Integer.parseInt(nAndSum[1]);
        int[] arr = Arrays.stream(lines[1].split("\\s+")).mapToInt(Integer::parseInt).toArray();

        long count = solve(sum, arr);
        //System.out.println("sum=" + sum + ", arr=" + Arrays.toString(arr) + ", count=" + count);
        System.out.println(count);
    }

    // target: [0, 1000]
    // values.length: [1, 1000]
    public static long solve(int target, int[] values) {
        int iCount = values.length + 1;
        int jCount = target + 1;
        // dp[i][j]
        // 在 数组前i个数字 中任选组合，使得加和为j时，方案的最大个数为 dp[i][j]
        long[][] dp = new long[iCount][jCount];

        for (int j = 0; j < jCount; j++) {
            // 在 数组前1个数字 中任选组合，使得加和为j时，方案的最大个数为 dp[1][j]
            dp[1][j] = (values[0] == j) ? 1 : 0;
        }

        // 在 数组前i个数字 中任选组合
        for (int i = 2; i < iCount; i++) {
            int val = values[i - 1];
            //使得加和为j
            for (int j = 1; j < jCount; j++) {
                // 不使用i时，就可以加和为j 的方案个数
                dp[i][j] = dp[i - 1][j];

                if (j == val) {
                    // 单单 values[i - 1] 就正好形成了一种方案
                    dp[i][j] = dp[i][j] + 1;
                    // 不使用i时，可以加和为 0 的方案个数
                    long tmp = dp[i - 1][0];
                    dp[i][j] = dp[i][j] + tmp;
                } else if (j > val) {
                    // 不使用i时，可以加和为 j-values[i-1] 的方案个数
                    long tmp = dp[i - 1][j - val];
                    dp[i][j] = dp[i][j] + tmp;
                }
                // values[i - 1]本身就已经 > j  了，任何方案都无法使用 values[i - 1] 啦
                else {

                }
            }

        }
        return dp[values.length][target];
    }

    public static void testIt() {
        int sum = 15;
        int[] arr = new int[]{5, 5, 10, 2, 3};
        long count = solve(sum, arr);
        System.out.println("sum=" + sum + ", arr=" + Arrays.toString(arr) + ", count=" + count);
    }
}

动态规划
设m[i][j]是前i个数 和为j的的最大组合方案数
递归公式
1 j=0 //j-a[i]为0时,表示a[i]=j,组合数为1
0 j<0
0 i<1且j!=0
M[i][j]=M[i-1][j]+M[i-1][j-a[i]] //前i-1个 和为j的最大组合数 + 前i-1个 和为 j-a[i]的最大组合数
例如 n=7 sum=8
数据为:5 1 2 4 3 2 3
得到如下矩阵
(i\j) 0 1 2 3 4 5 6 7 8
0 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 1 0 0 0
2 1 1 0 0 0 1 1 0 0
3 1 1 1 1 0 1 1 1 1
4 1 1 1 1 1 2 2 2 1
5 1 1 1 2 2 3 3 3 3
6 1 1 2 3 3 5 5 6 6
7 1 1 2 4 4 7 8 9 11
例如:m[7][9]=m[6][8]+m[6][8-3]=11
由于当前行只用到了上一行的数值,固可用二维数组存储

    public static void main(String[] args)throws Exception{
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        String[] strings=br.readLine().split("\\s");
        int n=Integer.parseInt(strings[0]);
        int sum=Integer.parseInt(strings[1]);
        strings=br.readLine().split("\\s");
        int[]data=new int[n];
        for(int i=0;i<n;i++){
            data[i]=Integer.valueOf(strings[i]);
        }
        dp(n,sum,data);
    }
    private static void dp(int n,int sum,int [] data){
        long[][] m=new long[2][sum+1];
        m[0][0]=1;//j=0
        m[1][0]=1;//j=0
        for(int i=1;i<=n;i++){
            for(int j=1;j<=sum;j++){
                if(j>=data[i-1]){
                    m[1][j]=m[0][j]+m[0][j-data[i-1]];
                }else {
                    m[1][j]=m[0][j];
                }
            }
//            System.out.println(Arrays.toString(m[0]));

            for(int k=0;k<=sum;k++){
                m[0][k]=m[1][k];
            }
        }
//        System.out.println(Arrays.toString(m[0]));
        System.out.println(m[0][sum]);
    }

import java.util.Scanner;

public class Main {
    public static long numberOfMethod(int[] A, int sum){
        long[] dp = new long[sum + 1]; //这里用long类型，用int只能80%
        dp[0] = 1;
        for (int i : A){
            for (int j = sum; j >= i; j--){
                dp[j] += dp[j - i];
            }
        }
        return dp[sum];
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            int n = sc.nextInt();
            int sum = sc.nextInt();
            int[] A = new int[n];
            for (int i = 0; i < n; i++){
                A[i] = sc.nextInt();
            }            
            System.out.println(numberOfMethod(A, sum));
        }
        sc.close();
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int sum = scanner.nextInt();
        int[] arr = new int[n+1];
        for (int i = 1; i <= n; i++) {
            arr[i] = scanner.nextInt();
        }

        System.out.println(calculate(arr, n, sum));
    }

    public static long calculate(int[] arr, int n, int sum) {
        long[][] dp = new long[n+1][sum + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= sum; j++) {
                if (j >= arr[i])
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-arr[i]];
                else
                    dp[i][j] = dp[i-1][j];
            }
        }
        return dp[n][sum];
    }
}

//不是很理解这个递推，很多人就直接写了，有没有人讲讲啊
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int count = in.nextInt();
            int sum = in.nextInt();
            int[] array = new int[count+1];
            for (int i = 1; i <= count; i++)
                array[i] = in.nextInt();

            long[][] dp = new long[count + 1][sum + 1];
            for (int i = 0; i <= count; i++)
                dp[i][0] = 1;

            for (int i = 1; i <= count; i++) {
                for (int j = 0; j <= sum; j++) {
                    if (j >= array[i])
                        dp[i][j] = dp[i-1][j] + dp[i-1][j-array[i]];
                    else
                        dp[i][j] = dp[i-1][j];
                }
            }
            System.out.println(dp[count][sum]);
        }
    }
}

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner cin = new Scanner(System.in);

		int n = cin.nextInt();
		int m = cin.nextInt();

		int arr[] = new int[n+1];
                //代表你使用前i个数组组成j的最大组合数
		long dp[][] = new long[n + 1][m + 1];
		for (int i = 1; i <= n; i++) {
			arr[i] = cin.nextInt();
		}

		
		for (int i = 0; i < m; i++) {
			dp[0][i] = 0;
		}
		//注意，你的dp[0][0]一定要是1，否则会出错
		for (int i = 0; i < n; i++) {
			dp[i][0] = 1;
		}
		
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (arr[i] <= j) {
					dp[i][j] = dp[i - 1][j] + dp[i - 1][j - arr[i]];
				} else {
					dp[i][j] = dp[i - 1][j];
				}
				
			}
			
		}

		System.out.println(dp[n][m]);
	}

}

//01背包问题的变形：根据数组前i-1个数相加和为j来决策加上第i个数是否符合条件，
//状态转移方程为f[i][j] = f[i-1][j] + f[i-1][j-target] (j>=target)
//其中f[i][j]表示数组前i个数中相加和为j的方案数
//f[i-1][j] 表示数组前i-1个数中相加和为j的方案数
//f[i-1][j-target]表示数组前i-1个数中相加和为j-target的方案数，要求j>=target,
//否则令f[i-1][j-target]=0；
// 以数组{3,2,10,5,5}，target=15为例：  
//以下表格从下往上，从左到右反映了状态的转移过程,理解了这个表格的建立过程，也就理解了01背包
// 
//  i  a[i]    1   2   3   4   5   6   7   8   9   10   11   12   13   14   15
//  4   5      0   1   1   0   3   0   2   2   0   4    0    2    2    0    4
//  3   5      0   1   1   0   2   0   1   1   0   2    0    1    1    0    2
//  2   10     0   1   1   0   1   0   0   0   0   1    0    1    1    0    1
//  1   2      0   1   1   0   1   0   0   0   0   0    0    0    0    0    0
//  0   3      0   0   1   0   0   0   0   0   0   0    0    0    0    0    0
import java.util.*;
public class Main{
    
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int target = in.nextInt();
        int[] a= new int[n];
        for(int i=0; i<n; ++i){
            a[i] = in.nextInt();
        }
        long res = dfs(a,target);
        System.out.println(res);
    }

    public static long dfs(int[] array, int target){
        long [][] dp = new long[array.length][target+1];

        //表示j-target为0时，方案数加1
        for (int i=0;i<array.length; ++i){
            dp[i][0] = 1;
        }

        for (int i=0; i<array.length; ++i){
            for (int j=1; j<=target; ++j){

                if (i == 0) {
                    dp[i][j] = j-array[i] == 0 ? 1 :  0;
                }else {
                    long temp = j - array[i] >= 0 ? dp[i-1][j - array[i]] : 0;
                    dp[i][j] = dp[i - 1][j] + temp;
                }
            }
        }
        return dp[array.length-1][target];
    }

}

package LineCode.Recruit2017.滴滴出行;

import java.util.Scanner;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {

            //输入
            int n = sc.nextInt();
            int sum = sc.nextInt();
            int[] arrs = new int[n];
            for (int i = 0; i < n; i++) {
                arrs[i] = sc.nextInt();
            }

            //处理
            long [] dp = new long[sum+1];
            dp[0] = 1;
            for (int i = 0; i < n; i++) {
                for (int j = sum; j >= arrs[i] ; j--)
                    dp[j] += dp[j-arrs[i]];
            }

            //输出
            System.out.println(dp[sum]);

        }
    }
}

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int sum = sc.nextInt();
		int [] A = new int[n];
		long [] f = new long[sum+1];
		for(int i=0;i<n;i++){
			A[i] = sc.nextInt();
		}
		f[0] = 1;
		for (int i=0;i<n;i++) {
	        for (int j=sum;j>=0;j--) {
	            if(j>=A[i]) {
	                f[j] += f[j-A[i]];
	            } 
	        }
	    }
		System.out.println(f[sum]);
	}
}