跳至主要內容

 

labuladong原创动态规划约 3477 字大约 12 分钟

Info

新版网站会员open in new window 限时优惠;算法可视化编辑器上线,点击体验open in new window

读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:

LeetCode力扣难度
494. Target Sumopen in new window494. 目标和open in new window🟠
-剑指 Offer II 102. 加减的目标值open in new window🟠

我们前文经常说回溯算法和递归算法有点类似,有的问题如果实在想不出状态转移方程,尝试用回溯算法暴力解决也是一个聪明的策略,总比写不出来解法强。

那么,回溯算法和动态规划到底是啥关系?它俩都涉及递归,算法模板看起来还挺像的,都涉及做「选择」,真的酷似父与子。

那么,它俩具体有啥区别呢?回溯算法和动态规划之间,是否可能互相转化呢?

今天就用力扣第 494 题「目标和open in new window」来详细对比一下回溯算法和动态规划,题目如下:

给你输入一个非负整数数组 nums 和一个目标值 target,现在你可以给每一个元素 nums[i] 添加正号 + 或负号 -,请你计算有几种符号的组合能够使得 nums 中元素的和为 target

函数的签名如下:

java 🟢
int findTargetSumWays(int[] nums, int 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 不就行了嘛?

伪码思路如下:

加载中...

上次编辑于: