【LeetCode】494. 目标和
LeetCode 目标
2023-09-14 09:13:24 时间
0.总结
- 本题难点在于抽象的能力,如何将本题抽象成一道动态规划题是关键。
1.题目
2.思想
2.1 深搜 + 剪枝
- (1)每个整数前只能加一个符号,每次都有两种选择
- (2)将得到的数字求和,判断是否可以得到想要的结果target
- (3)根据条件判断当前这个节点是否值得深搜
可惜的是,这个python下的代码过不完测试样例。
2.2 动态规划
初看题解,本题竟然还可以使用动态规划?!我是大大的震惊!但是这些题目考的就是抽象的分析能力,难点在于如何将本道题转换成一个动态规划需要解决的题?于是有了下面这段分析。
3.代码
3.1 深搜+剪枝
下面这个代码的ac情况如下:
class Solution:
def __init__(self):
self.res = 0
def findTargetSumWays(self, nums: List[int], target: int) -> int:
post_sum = [0] * (len(nums)+1) # 记录后n项和
for i in reversed(range(len(nums))):
post_sum[i] = post_sum[i+1] + nums[i]
# print(post_sum)
# 当前正在访问第idx个元素
self.dfs(target,nums,idx=0,tmp=[],post_sum=post_sum)
return self.res
# idx 表示当前正在访问的下标数字
def dfs(self,target,nums,idx,tmp,post_sum):
# 剪枝
# 如果当前的和减去
if sum(tmp) - post_sum[idx] > target:
return
if sum(tmp) + post_sum[idx] < target:
return
if idx==len(nums) :
# print(tmp)
if sum(tmp) == target:
self.res += 1
return
# 修改为+
tmp.append(nums[idx])
self.dfs(target,nums,idx+1,tmp,post_sum)
tmp.pop()
# 修改为-
tmp.append(-nums[idx])
self.dfs(target,nums,idx+1,tmp,post_sum)
tmp.pop()
'''
[16,40,9,17,49,32,30,10,38,36,31,22,3,36,32,2,26,17,30,47]
49
'''
3.2 动态规划
~
相关文章
- Java实现 LeetCode 766 托普利茨矩阵(暴力)
- Java实现 LeetCode 820 单词的压缩编码(字典树)
- Java实现 LeetCode 494 目标和
- Java实现 LeetCode 494 目标和
- Java实现 LeetCode 493 翻转对
- Java实现 LeetCode 478 在圆内随机生成点
- Java实现 LeetCode 451 根据字符出现频率排序
- Java实现 LeetCode 423 从英文中重建数字
- LeetCode(28): 实现strStr()
- LeetCode(4):两个排序数组的中位数
- LeetCode(30):与所有单词相关联的字串
- LeetCode-1615. 最大网络秩【图】
- LeetCode-1779. 找到最近的有相同 X 或 Y 坐标的点【数组】
- LeetCode-891. 子序列宽度之和【排序,数学,数组】
- Leetcode 1566. 重复至少 K 次且长度为 M 的模式(有点意思)
- Leetcode 744. 寻找比目标字母大的最小字母
- Leetcode 2089. 找出数组排序后的目标下标
- leetcode 766. Toeplitz Matrix
- 【Leetcode刷题Python】LeetCode 478. 在圆内随机生成点
- 【14】最长公共前缀【LeetCode】