题目

https://leetcode.com/problems/target-sum/

题解

经典 dp，直接看草稿：

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int n : nums) {
            sum += n;
        }
        if (Math.abs(target) > sum) return 0;

        int[][] dp = new int[nums.length][2 * sum + 1];
        int OFFSET = sum;
        dp[0][-nums[0] + OFFSET] += 1;
        dp[0][+nums[0] + OFFSET] += 1; // 不能写成=1，因为可能和上一行重合
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < 2 * sum + 1; j++) {
                int L = 0, R = 0;
                if (j - nums[i] >= 0) L = dp[i - 1][j - nums[i]];
                if (j + nums[i] < 2 * sum + 1) R = dp[i - 1][j + nums[i]];
                dp[i][j] = L + R;
            }
        }
        return dp[nums.length - 1][target + OFFSET];
    }
}