标签搜索

目 录CONTENT

文章目录

力扣--目标和.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 5 阅读 / 6,393 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

力扣--目标和

@[toc]

一、题目描述

在这里插入图片描述
在这里插入图片描述

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {

    }
};

二、分析

方法一:枚举

class Solution {
public:
	//保存结果
    int count = 0;
    //start代表当前在nums的下标索引
    //sum代表当前+/-运算之后的结果
    //target代表目标结果
    void dp(vector<int>& nums, int start, int sum, int target)
    {
    	//遍历完数组并且sum和target相等才++count
        if(start == nums.size())
        {
            if(target == sum)
            {
                count++;
            }
            return ;
        }
	
		//+
        dp(nums,start + 1,sum + nums[start],target);
        
        //-
        dp(nums,start + 1,sum - nums[start],target);
    }
    
    int findTargetSumWays(vector<int>& nums, int S) 
    {
        if(nums.empty())
        {
            return 0;
        }

        dp(nums, 0, 0, S);
        return count;
    }
};

方法二:回溯【超时】

  •  任何算法的核心都是穷举,回溯算法就是一个暴力穷举算法,回溯算法框架:
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择
  •  关键就是搞清楚什么是「选择」,而对于这道题,「选择」不是明摆着的吗?
  •  对于每个数字 nums[i],我们可以选择给一个正号 + 或者一个负号 -,然后利用回溯模板穷举出来所有可能的结果,数一数到底有几种组合能够凑出 target 不就行了嘛?
  •  伪码思路如下:
def backtrack(nums, i):
    if i == len(nums):
        if 达到 target:
            result += 1
        return

    for op in { +1, -1 }:
        选择 op * nums[i]
        # 穷举 nums[i + 1] 的选择
        backtrack(nums, i + 1)
        撤销选择
  •  代码
int result = 0;

/* 主函数 */
int findTargetSumWays(int[] nums, int target) {
    if (nums.length == 0) 
    	return 0;
    backtrack(nums, 0, target);
    return result;
}

/* 回溯算法模板 */
void backtrack(int[] nums, int i, int rest) 
{
    // base case
    if (i == nums.length) 
    {
        if (rest == 0) 
        {
            // 说明恰好凑出 target
            result++;
        }
        return;
    }
    
    // 给 nums[i] 选择 - 号
    rest += nums[i];
    
    // 穷举 nums[i + 1]
    backtrack(nums, i + 1, rest);
    
    // 撤销选择
    rest -= nums[i]; 

    // 给 nums[i] 选择 + 号
    rest -= nums[i];
    
    // 穷举 nums[i + 1]
    backtrack(nums, i + 1, rest);
    
    // 撤销选择
    rest += nums[i];
}
  •  有的读者可能问,选择 - 的时候,为什么是 rest += nums[i],选择 + 的时候,为什么是 rest -= nums[i] 呢,是不是写反了?
  •  不是的,「如何凑出 target」和「如何把 target 减到 0」其实是一样的。我们这里选择后者,因为前者必须给 backtrack 函数多加一个参数,我觉得不美观:
void backtrack(int[] nums, int i, int sum, int target) {
    // base case
    if (i == nums.length) 
    {
        if (sum == target) 
        {
            result++;
        }
        return;
    }
    // ...
}
  •  因此,如果我们给 nums[i] 选择 + 号,就要让 rest - nums[i],反之亦然。
  •  以上回溯算法可以解决这个问题,时间复杂度为$O(2^N)$,N 为 nums 的大小。
  •  进一步观察发现这个回溯算法就是个二叉树的遍历问题:
void backtrack(int[] nums, int i, int rest) {
    if (i == nums.length) 
    {
        return;
    }
    backtrack(nums, i + 1, rest - nums[i]);
    backtrack(nums, i + 1, rest + nums[i]);
}
  •  树的高度就是 nums 的长度嘛,所以说时间复杂度就是这棵二叉树的节点数,为 $O(2^N)$,其实是非常低效的。

方法三:消除重叠子问题【超时】

  •  动态规划之所以比暴力算法快,是因为动态规划技巧消除了重叠子问题。
  •  如何发现重叠子问题?看是否可能出现重复的「状态」。对于递归函数来说,函数参数中会变的参数就是「状态」,对于 backtrack 函数来说,会变的参数为 i 和 rest。
  •  先抽象出递归框架:
void backtrack(int i, int rest) {
    backtrack(i + 1, rest - nums[i]);
    backtrack(i + 1, rest + nums[i]);
}
  •  举个简单的例子,如果 nums[i] = 0,会发生什么?
void backtrack(int i, int rest) {
    backtrack(i + 1, rest);
    backtrack(i + 1, rest);
}
  •  你看,这样就出现了两个「状态」完全相同的递归函数,无疑这样的递归计算就是重复的。
  •  这就是重叠子问题,而且只要我们能够找到一个重叠子问题,那一定还存在很多的重叠子问题。
  •  因此,状态 (i, rest) 是可以用备忘录技巧进行优化的:
int findTargetSumWays(int[] nums, int target) {
    if (nums.length == 0) 
    	return 0;
    return dp(nums, 0, target);
}

// 备忘录
HashMap<String, Integer> memo = new HashMap<>();
int dp(int[] nums, int i, int rest) {
    // base case
    if (i == nums.length) 
    {
        if (rest == 0) 
        	return 1;
        return 0;
    }
    
    // 把它俩转成字符串才能作为哈希表的键
    String key = i + "," + rest;
    
    // 避免重复计算
    if (memo.containsKey(key)) 
    {
        return memo.get(key);
    }
    
    // 还是穷举
    int result = dp(nums, i + 1, rest - nums[i]) + dp(nums, i + 1, rest + nums[i]);
    
    // 记入备忘录
    memo.put(key, result);
    return result;
}
  •  这个解法通过备忘录消除了很多重叠子问题,效率有一定的提升,但是这就结束了吗?

方法四:动态规划

  •  事情没有这么简单,先来算一算,消除重叠子问题之后,算法的时间复杂度是多少?其实最坏情况下依然是 $O(2^N)$。
  •  为什么呢?因为我们只不过恰好发现了重叠子问题,顺手用备忘录技巧给优化了,但是底层思路没有变,依然是暴力穷举的回溯算法,依然在遍历一棵二叉树。
  •  这只能叫对回溯算法进行了「剪枝」,提升了算法在某些情况下的效率,但算不上质的飞跃。
  •  其实,这个问题可以转化为一个子集划分问题,而子集划分问题又是一个典型的背包问题。动态规划总是这么玄学,让人摸不着头脑……
  •  首先,如果我们把 nums 划分成两个子集 A 和 B,分别代表分配 + 的数和分配 - 的数,那么他们和 target 存在如下关系:
sum(A) - sum(B) = target
sum(A) = target + sum(B)
sum(A) + sum(A) = target + sum(B) + sum(A)
2 * sum(A) = target + sum(nums)
  •  综上,可以推出 $sum(A) = (target + sum(nums)) / 2$ ,也就是把原问题转化成:nums 中存在几个子集A,使得 A 中元素的和为$(target + sum(nums)) / 2$?
  •  类似的子集划分问题我们前文 经典背包问题:子集划分 讲过,现在实现这么一个函数:
/* 计算 nums 中有几个子集的和为 sum */
int subsets(int[] nums, int sum) {}

//然后,可以这样调用这个函数:
int findTargetSumWays(int[] nums, int target) {
    int sum = 0;
    for (int n : nums) 
    	sum += n;
    	
    // 这两种情况,不可能存在合法的子集划分
    if (sum < target || (sum + target) % 2 == 1) 
    {
        return 0;
    }
    return subsets(nums, (sum + target) / 2);
}
  •  好的,变成背包问题的标准形式:
  •  有一个背包,容量为 sum,现在给你 N 个物品,第 i 个物品的重量为 nums[i - 1](注意 1 <= i <= N),每个物品只有一个,请问你有几种不同的方法能够恰好装满这个背包
  •  现在,这就是一个正宗的动态规划问题了,下面按照我们一直强调的动态规划套路走流程:
  •  第一步要明确两点,「状态」和「选择」
  •  对于背包问题,这个都是一样的,状态就是「背包的容量」和「可选择的物品」,选择就是「装进背包」或者「不装进背包」。
  •  第二步要明确 dp 数组的定义。
  •  按照背包问题的套路,可以给出如下定义:
  •  dp[i][j] = x 表示,若只在前 i 个物品中选择,若当前背包的容量为 j,则最多有 x 种方法可以恰好装满背包。
  •  翻译成我们探讨的子集问题就是,若只在 nums 的前 i 个元素中选择,若目标和为 j,则最多有 x 种方法划分子集。
  •  根据这个定义,显然 dp[0][..] = 0,因为没有物品的话,根本没办法装背包;dp[..][0] = 1,因为如果背包的最大载重为 0,「什么都不装」就是唯一的一种装法。
  •  我们所求的答案就是 dp[N][sum],即使用所有 N 个物品,有几种方法可以装满容量为 sum 的背包。
  •  第三步,根据「选择」,思考状态转移的逻辑。
  •  回想刚才的 dp 数组含义,可以根据「选择」对 dp[i][j] 得到以下状态转移:
  •  如果不把 nums[i] 算入子集,或者说你不把这第 i 个物品装入背包,那么恰好装满背包的方法数就取决于上一个状态dp[i-1][j],继承之前的结果
  •  如果把 nums[i] 算入子集,或者说你把这第 i 个物品装入了背包,那么只要看前 i - 1 个物品有几种方法可以装满 j -nums[i-1] 的重量就行了,所以取决于状态 dp[i-1][j-nums[i-1]]
  •  PS:注意我们说的 i 是从 1 开始算的,而数组 nums 的索引时从 0 开始算的,所以 nums[i-1] 代表的是第 i个物品的重量,j - nums[i-1] 就是背包装入物品 i 之后还剩下的容量。
  •  由于 dp[i][j] 为装满背包的总方法数,所以应该以上两种选择的结果求和,得到状态转移方程:
  •  $dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]$;
  •  然后,根据状态转移方程写出动态规划算法:
/* 计算 nums 中有几个子集的和为 sum */
int subsets(int[] nums, int sum) 
{
    int n = nums.length;
    int[][] dp = new int[n + 1][sum + 1];
    
    // base case
    for (int i = 0; i <= n; i++) 
    {
        dp[i][0] = 1;
    }

    for (int i = 1; i <= n; i++) 
    {
        for (int j = 0; j <= sum; j++) 
        {
            if (j >= nums[i-1]) 
            {
                // 两种选择的结果之和
                dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
            } 
            else 
            {
                // 背包的空间不足,只能选择不装物品 i
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[n][sum];
}
  •  然后,发现这个 dp[i][j] 只和前一行 dp[i-1][..] 有关,那么肯定可以优化成一维 dp:
/* 计算 nums 中有几个子集的和为 sum */
int subsets(int[] nums, int sum) 
{
    int n = nums.length;
    int[] dp = new int[sum + 1];
    
    // base case
    dp[0] = 1;

    for (int i = 1; i <= n; i++) 
    {
        // j 要从后往前遍历
        for (int j = sum; j >= 0; j--) 
        {
            // 状态转移方程
            if (j >= nums[i-1]) 
            {
                dp[j] = dp[j] + dp[j-nums[i-1]];
            } 
            else 
            {
                dp[j] = dp[j];
            }
        }
    }
    return dp[sum];
}
  •  对照二维 dp,只要把 dp 数组的第一个维度全都去掉就行了,唯一的区别就是这里的 j 要从后往前遍历,原因如下:
  •  因为二维压缩到一维的根本原理是,$dp[j] 和 dp[j-nums[i-1]]$ 还没被新结果覆盖的时候,相当于二维 dp 中的$dp[i-1][j] 和 dp[i-1][j-nums[i-1]]$。
  •  那么,我们就要做到:在计算新的 dp[j] 的时候,dp[j] 和 dp[j-nums[i-1]] 还是上一轮外层 for循环的结果
  •  如果你从前往后遍历一维 dp 数组,dp[j] 显然是没问题的,但是 dp[j-nums[i-1]] 已经不是上一轮外层 for循环的结果了,这里就会使用错误的状态,当然得不到正确的答案。
  •  完整C++代码
class Solution {
public:
    /* 计算 nums 中有几个子集的和为 sum */
	int subsets(vector<int>& nums, int sum) 
	{
    	int n = nums.size();
    	vector<int> dp (sum + 1,0);
    
    	// base case
   		dp[0] = 1;

    	for (int i = 1; i <= n; i++) 
    	{
        	// j 要从后往前遍历
        	for (int j = sum; j >= 0; j--) 
        	{
            	// 状态转移方程
            	if (j >= nums[i-1]) 
            	{
                	dp[j] = dp[j] + dp[j-nums[i-1]];
            	} 
            	else 
            	{
                	dp[j] = dp[j];
            	}
        	}
    	}
    	return dp[sum];
	}
    int findTargetSumWays(vector<int>& nums, int S) {
        if(nums.empty())
        {
            return 0;
        }

        int sum = 0;
        for(auto e : nums)
        {
            sum += e;
        }
        
        if (sum < S || (sum + S) % 2 == 1) 
        {
            return 0;
        }

        int target = (sum + S) / 2;
        return subsets(nums, target);
    }
};
  •  现在,这道题算是彻底解决了。
  •  总结一下,回溯算法虽好,但是复杂度高,即便消除一些冗余计算,也只是「剪枝」,没有本质的改进
  •  而动态规划就比较玄学了,经过各种改造,从一个加减法问题变成子集问题,又变成背包问题,经过各种套路写出解法,又搞出状态压缩,还得反向遍历。
0

评论区