🌕 🌕 494. 目标和

难度: 🌕 🌕

• 问题描述
• 解法
• 输出

问题描述

---

解法

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        // 思路：
        // pos + neg = sum
        // pos - neg = target
        // =>
        // pos = (sum + target) / 2
        // neg = (sum - target) / 2
        // 背包问题
        int sum = 0;
        for(int i : nums) {
            sum += i;
        }
        // 特殊情况特判
        if(Math.abs(target) > Math.abs(sum)) {
            return 0;
        }
        int res = sum + target;
        if((res & 1) == 1) {
            return 0;
        }
        res /= 2;
        // dp[i] : 重量为 i 时有多少种情况
        int[] dp = new int[res + 1];
        dp[0] = 1;
        int len = nums.length;
        for(int j = 0; j < len; j ++) {
            for(int i = res; i - nums[j] >= 0; i --) {
                dp[i] += dp[i - nums[j]];
            }
        }
        return dp[res];
    }
}

---

输出