原创动态规划约 3465 字大约 12 分钟
Info
新版网站会员 即将涨价;已支持老用户续费~
读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
LeetCode | 力扣 | 难度 |
---|---|---|
494. Target Sum | 494. 目标和 | 🟠 |
- | 剑指 Offer II 102. 加减的目标值 | 🟠 |
我们前文经常说回溯算法和递归算法有点类似,有的问题如果实在想不出状态转移方程,尝试用回溯算法暴力解决也是一个聪明的策略,总比写不出来解法强。
那么,回溯算法和动态规划到底是啥关系?它俩都涉及递归,算法模板看起来还挺像的,都涉及做「选择」,真的酷似父与子。
![](/algo/images/targetSum/1.jpg)
那么,它俩具体有啥区别呢?回溯算法和动态规划之间,是否可能互相转化呢?
今天就用力扣第 494 题「目标和」来详细对比一下回溯算法和动态规划,题目如下:
给你输入一个非负整数数组 nums
和一个目标值 target
,现在你可以给每一个元素 nums[i]
添加正号 +
或负号 -
,请你计算有几种符号的组合能够使得 nums
中元素的和为 target
。
函数的签名如下:
java 🟢
int findTargetSumWays(int[] nums, int target);
cpp 🤖
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
int findTargetSumWays(vector<int>& nums, int target);
python 🤖
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
def findTargetSumWays(nums: List[int], target: int) -> int:
go 🤖
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
func findTargetSumWays(nums []int, target int) int {
javascript 🤖
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
var findTargetSumWays = function(nums, target) {};
比如说输入 nums = [1,3,1,4,2], target = 5
,算法返回 3,因为有如下 3 种组合能够使得 target
等于 5:
-1+3+1+4-2=5
-1+3+1+4-2=5
+1-3+1+4+2=5
nums
的元素也有可能包含 0,我们可以正常地给 0 分配正负号。
一、回溯思路
其实我第一眼看到这个题目,花了两分钟就写出了一个回溯解法。
任何算法的核心都是穷举,回溯算法就是一个暴力穷举算法,前文 回溯算法解题框架 就写了回溯算法框架:
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
关键就是搞清楚什么是「选择」,而对于这道题,「选择」不是明摆着的吗?对于每个数字 nums[i]
,我们可以选择给一个正号 +
或者一个负号 -
,然后利用回溯模板穷举出来所有可能的结果,数一数到底有几种组合能够凑出 target
不就行了嘛?
伪码思路如下: