小美的数组构造

菜狗的简单暴力。 等一个大佬的更强解法。
dp[i][j] 表示在填到第i个数时，总和如果为j的构造方式。
那么i = 0时， 除了j= nums[0]和j= 0. 其他的构造方式都为1.
那么为了方便考虑，就枚举i>0时， 如果当前填写数字[1,sum]会对当前的数组dp[i]造成的影响。
同时考虑到这是个markov过程，所以使用滚动数组优化。
顺便一提，总感觉如果把二维数组表示成在坐标i处，当前和<=j的可行构造数能把复杂度降很多。

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    final static int MOD = 1000_000_007;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n]; int sum = 0;
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
            sum += nums[i];
        }

        // markov 过程 ， 滚动数组简化空间
        // dp[i][j]: i表示填到第几个, J 表示当前总和。
        int[][] dp = new int[2][sum+1];
        for (int i = 0; i <= sum; i++) dp[0][i] = 1; 
        dp[0][0] = 0; dp[0][nums[0]] = 0;
        for (int i = 1; i < n; i++) {
            int index = i % 2;
            int pre = 1-index;

            for (int kk = 0; kk <= sum; kk++) dp[index][kk] = 0; // 滚动数组清零
            for (int j = 1; j <= sum; j ++) { // 当前填的数字
                if (j == nums[i]) continue; // 不同
                for (int count = j+1; count <= sum; count ++) { // 当前的组合值。
                    int preN = count - j;  // 填
                    dp[index][count] += dp[pre][preN];
                    dp[index][count] %= MOD;
                }
            }
        }

        int index = (n-1)%2;
        System.out.println(dp[index][sum]);
    }
}

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static final int N = (int)1e9 + 7;
    static int[][] memo;
    static int[] arr;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        arr = new int[n];
        int sum = 0;
        for (int i = 0 ; i < n ; i++) {
            arr[i] = in.nextInt();
            sum += arr[i];
        }
        memo = new int[n][510];
        for (int i = 0 ; i < n ; i++) {
            Arrays.fill(memo[i], -1);
        }
        System.out.println(dfs(0, sum));

    }
    private static int dfs(int cur, int sum) {
        if (sum < 0) return 0;
        if (cur == arr.length) {
            return sum == 0 ? 1 : 0;
        }
        if (memo[cur][sum] != -1) return memo[cur][sum];
        int ans = 0;
        for (int i = 1 ; i <= sum; i++) {
            if (i == arr[cur]) continue;
            ans = (ans + dfs(cur + 1, sum - i)) % N;
        }
        memo[cur][sum] = ans;
        return ans;
    }
}