算法分析

注意:

• 1、由于是求的是方案数，因此f[i,j] = f[i - 1][j] + f[i][j - v]

• 2、初始化f[i][0] = 1

时间复杂度$O(n^2)$

参考文献

算法提高课

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int N = 10010;
    static int[] f = new int[N];
    static int n;
    static int m;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = reader.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int m = Integer.parseInt(s1[1]);
        String[] s2 = reader.readLine().split(" ");
        f[0] = 1;
        for(int i = 1;i <= n;i++)
        {
            int v = Integer.parseInt(s2[i - 1]);
            for(int j = m;j >= v;j --)
            {
                f[j] = f[j] + f[j - v];
            }
        }
        System.out.println(f[m]);
    }
}