494. 目标和

494. 目标和

一看数据最多才20个，直接暴力DFS感觉能过，没想到真过了o(╯□╰)o

class Solution {
    int ans = 0;
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;

        dfs(0,n,0,target,nums);

        return ans;
    }

    private void dfs(int i, int n,int cur, int target, int[] nums) {
        if (i == n) {
            if (cur == target) ans++;
            return;
        }

        for (int k = 0;k<2;k++) {
            int p = 1;
            if (k==1) {
                p = -1;
            }
            dfs(i+1,n,cur + p * nums[i],target,nums);
        }
    }
}

动态规划解法：

todo