目标和问题:背包问题的变体
原创动态规划约 3388 字
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准,解决了之前 chatGPT 翻译可能出错的问题~
读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
LeetCode | 力扣 | 难度 |
---|---|---|
494. Target Sum | 494. 目标和 | 🟠 |
- | 剑指 Offer II 102. 加减的目标值 | 🟠 |
我们前文经常说回溯算法和递归算法有点类似,有的问题如果实在想不出状态转移方程,尝试用回溯算法暴力解决也是一个聪明的策略,总比写不出来解法强。
那么,回溯算法和动态规划到底是啥关系?它俩都涉及递归,算法模板看起来还挺像的,都涉及做「选择」,真的酷似父与子。
![](/algo/images/targetSum/1.jpg)
那么,它俩具体有啥区别呢?回溯算法和动态规划之间,是否可能互相转化呢?
今天就用力扣第 494 题「目标和」来详细对比一下回溯算法和动态规划,题目如下:
494. 目标和 | 力扣 | LeetCode |
给你一个非负整数数组 nums
和一个整数 target
。
向数组中的每个整数前添加 '+'
或 '-'
,然后串联起所有整数,可以构造一个 表达式 :
- 例如,
nums = [2, 1]
,可以在2
之前添加'+'
,在1
之前添加'-'
,然后串联起来得到表达式"+2-1"
。
返回可以通过上述方法构造的、运算结果等于 target
的不同 表达式 的数目。
示例 1:
输入:nums = [1,1,1,1,1], target = 3 输出:5 解释:一共有 5 种方法让最终目标和为 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3
示例 2:
输入:nums = [1], target = 1 输出:1
提示:
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
函数的签名如下:
java 🟢
int findTargetSumWays(int[] nums, int target);
cpp 🤖
int findTargetSumWays(vector<int>& nums, int target);
python 🤖
def findTargetSumWays(nums: List[int], target: int) -> int:
go 🤖
func findTargetSumWays(nums []int, target int) int {
javascript 🤖
var findTargetSumWays = function(nums, target) {};
一、回溯思路
其实我第一眼看到这个题目,花了两分钟就写出了一个回溯解法。
任何算法的核心都是穷举,回溯算法就是一个暴力穷举算法,前文 回溯算法解题框架 就写了回溯算法框架:
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
关键就是搞清楚什么是「选择」,而对于这道题,「选择」不是明摆着的吗?对于每个数字 nums[i]
,我们可以选择给一个正号 +
或者一个负号 -
,然后利用回溯模板穷举出来所有可能的结果,数一数到底有几种组合能够凑出 target
不就行了嘛?
伪码思路如下: