剑指 Offer II 102. 加减的目标值-DFS+动态规划Java实现

目录

1.题目

2.思路

方法1——DFS——570ms

代码

时间复杂度——O（2^n）

空间复杂度——O（n）

方法2——动态规划——3ms

代码

时间复杂度——O（n * pos）

空间复杂度——O（n * pos）

3.结果

---

1.题目

2.思路 方法1——DFS——570ms

看见这个题，第一想法就是DFS，也可以叫回溯的思想。对于每个元素，都有+ 和 -两种 *** 作，总共有n个元素，所以时间复杂度为2^n。n的最大值为20，所以时间2^10约等于10^6，并不会超时。

代码

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

    public void dfs(int[]nums, int sum, int target, int index){
        int n = nums.length;
        if(index > n) return ;
        if(n == index){
            
            if(sum == target){
                ans++;
            }
            return ;
        }
        // System.out.println(sum +">>>");
        dfs(nums, sum + nums[index], target, index + 1);

        dfs(nums, sum - nums[index], target, index + 1);
        return ;
    }
}

时间复杂度——O（2^n）

分析如上。

空间复杂度——O（n）

空间复杂度来源于栈空间的深度，也就是数组nums的长度。

方法2——动态规划——3ms

一般求解个数的题，都很有可能用到动态规划来解决。我一开始想的二维dp[i][j]的意思为前i个数的加减组成和为j的个数（直接套用题目的问题！），这样子的转移方程想的可以是dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]].但是这样子初始化的时候，是存在问题的，而且还有个问题是当前元素依赖于后面的元素，似乎是行不通的。所以还是定义不太对。

这里的问题的本质是一个0-1背包问题，不看题解自己不知道。。。看了题解，发现真的奇妙！！！

定义：dp[i][j]为前i个数中选择某些数组成和为j的个数（注意区分原来的定义），意思说前面i个数有的数可以选，有的数不选，选了的数，那么就直接用+。

那么j的范围应该是多少呢？

首先j代表的意思是nums数组中选取某些数组成的和。这个和题中要求的target的关系是什么？

假如我们设定数组中正数的和为pos, 负数的和为neg,那么必然存在两个等式。

pos + neg = target

pos - neg = sum.(所有数字的和)

化简可以得到pos = (target + sum) / 2;这个值就是j的最大值！！！

那么状态方程是什么？

dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]]

那么初始化值呢？

dp[i][0] = 1(因为都不选，就肯定有一种方案组成和为0)

代码

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        // 动态规划 -- 0-1背包，没想过
        int n = nums.length;
        int sum = 0;
        for(int i = 0 ; i < n ; i++)
            sum += nums[i];
        int posSum = (target + sum) % 2 == 0 ? (target + sum) / 2 : 0;
        // System.out.println(posSum);

        if((target + sum) % 2 != 0 || sum < target) return 0;

        // 定义.前i个数选取某些元素组成和为j的个数
        int[][]dp = new int[n + 1][posSum + 1];

        // 初始化
        for(int i = 0 ; i <= n ; i++)
            dp[i][0] = 1;

        // 状态转移
        for(int i = 1 ; i <= n; i++){
            for(int j = 0; j <= posSum ; j++){ //这里j是从0开始的！！！
                if(j >= nums[i - 1])
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
                else 
                    dp[i][j] = dp[i - 1][j];
            }
            
        }
        
        return dp[n][posSum];
    }
}

时间复杂度——O（n * pos）

两个for循环。

空间复杂度——O（n * pos）

二维dp

3.结果