代码随想录算法训练营Day35

卡码网46.携带研究材料
力扣494.目标和【meidum】
力扣416.分割等和子集【medium】

一、卡码网46.携带研究材料

题目链接：卡码网46.携带研究材料

视频链接：代码随想录
题解链接：代码随想录

1、思路

• 

• 

• 

• dp[i][j] 表示从下标为 [0-i] 的物品里任意取，放进容量为 j 的背包，价值总和最大是多少

• 状态转移方程 ：$dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])$

• 

• 时间复杂度：$O(M\ast N)$

2、代码

import sys
def main():data = sys.stdin.read().strip().split()ptr = 0M = int(data[ptr])ptr += 1N = int(data[ptr])ptr += 1weight = list(map(int,data[ptr : ptr + M]))ptr += Mvalue = list(map(int, data[ptr : ptr + M]))dp = [[0] * (N + 1) for _ in range(M)]for j in range(weight[0], N + 1):dp[0][j] = value[0]for i in range(1,M):for j in range(N + 1):if j < weight[i]:dp[i][j] = dp[i - 1][j]else:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])print(dp[M - 1][N])if __name__ == "__main__":main() 

3、代码问题

• map() 是一个内置函数，它的作用是将一个函数应用到可迭代对象（如列表、元组等）的每个元素上，并返回一个迭代器。
• 模板

import sysdef solve():# 读取所有输入并分割data = sys.stdin.read().split()ptr = 0# 按需读取数据n = int(data[ptr])ptr += 1m = int(data[ptr])ptr += 1arr = list(map(int, data[ptr:ptr+n]))ptr += n# 计算逻辑result = sum(arr) * m# 输出结果print(result)if __name__ == "__main__":solve()

---

二、力扣494.目标和【meidum】

题目链接：力扣494.目标和

视频链接：代码随想录
题解链接：灵茶山艾府

1、思路

• 

• 时间复杂度：$O(mn)$其中 $n$ 为 $nums$的长度，$m$ 为 $nums$ 的元素和减去 $target$ 的绝对值。

• 由于每个状态只会计算一次，动态规划的时间复杂度 = 状态个数 × 单个状态的计算时间。

• 本题状态个数等于 $O(nm)$，单个状态的计算时间为 $O(1)$，所以动态规划的时间复杂度为 $O(nm)$。

• 空间复杂度：$O(nm)$。保存多少状态，就需要多少空间。

2、代码

class Solution:def findTargetSumWays(self, nums: List[int], target: int) -> int:# p + q = s = sum(nums)# p - q = target# 故：p = s + target / 2；q = s - target / 2s = sum(nums) -  abs(target)if s < 0 or s % 2:return 0m = s // 2@cachedef dfs(i:int, c:int) -> int: # 表示从前i个数中选一些数恰好组成c的 方案数目if i < 0:return 1 if c == 0 else 0if c < nums[i]:return dfs(i - 1, c)return dfs(i - 1, c) + dfs(i - 1, c - nums[i])return dfs(len(nums) - 1, m)

• 1:1 翻译成递推
• 时间空间复杂度和回溯+记忆搜索一致

class Solution:def findTargetSumWays(self, nums: List[int], target: int) -> int:# p + q = s = sum(nums)# p - q = target# 故：p = s + target / 2；q = s - target / 2s = sum(nums) -  abs(target)if s < 0 or s % 2:return 0m = s // 2n = len(nums)f = [ [0] * (m + 1) for _ in range(n + 1)]f[0][0] = 1for i, x in enumerate(nums):for c in range(m + 1):if c < x:f[i + 1][c] = f[i][c]else:f[i + 1][c] = f[i][c] + f[i][c - x]return f[n][m]

• 空间优化：1个数组
• 时间复杂度：$O(nm)$，其中 $n$ 为 $nums$ 的长度，$m$ 为 $nums$ 的元素和减去 $target$ 的绝对值。
  空间复杂度：$O(m)$。

class Solution:def findTargetSumWays(self, nums: List[int], target: int) -> int:# p + q = s = sum(nums)# p - q = target# 故：p = s + target / 2；q = s - target / 2s = sum(nums) -  abs(target)if s < 0 or s % 2:return 0m = s // 2f = [1] + [0] * mfor x in nums:for c in range(m, x - 1, -1):f[c] += f[c - x]return f[m]

---

三、力扣416.分割等和子集【medium】

题目链接：力扣416.分割等和子集
视频链接：代码随想录
题解链接：灵茶山艾府

1、思路

• $s=sum(nums)$，找出子集和为 $\frac{s}{2}$
• 从$nums$中选出一个子序列，其元素和为$\frac{s}{2}$
• $dfs(i,j)$：从 $nums[0]$ 到 $nums[i]$ 中恰好选出 = j 的子序列
• 时间复杂度：$O(n\ast \frac{s}{2})$

2、代码

回溯 + 缓存器 = 记忆化搜索

• 时间复杂度：$O(n\ast \frac{s}{2})$
• 空间复杂度：$O(n\ast \frac{s}{2})$

class Solution:def canPartition(self, nums: List[int]) -> bool:@cachedef dfs(i:int, j:int) -> bool:if i < 0:return j == 0return j >=nums[i] and dfs(i - 1, j - nums[i]) or dfs(i - 1, j)s = sum(nums)return s % 2 == 0 and dfs(len(nums)- 1, s)

翻译成递推

• 为了边界条件，所有的 i 都 + 1处理
• 构造 $(n+1)\ast (s+1)$矩阵
• 时间复杂度：$O(n\ast \frac{s}{2})$
• 空间复杂度：$O(n\ast \frac{s}{2})$

class Solution:def canPartition(self, nums: List[int]) -> bool:s = sum(nums)if s % 2:return Falses //= 2n = len(nums)f = [[False] * (s + 1) for _ in range(n + 1)]f[0][0] = Truefor i, x in enumerate(nums):for j in range(s + 1):if j >= x and f[i][j - x]:f[i + 1][j] = Trueelse:f[i + 1][j] = f[i][j]return f[n][s]

空间优化

• 逆序排序：避免正序的重复计数
• $s_2=min(s_2+x,s)$
  • 当 $s_2+x<=s$：即使加上x，当前的总和最多到达 s2 + x ，所以s2 + x 到 s 这个范围是达不到的，不用做无用的计算，默认是 False
  • 当 $s_2+x>s$：我们的目标是 s ，超过的部分不用检查
• 
• 时间复杂度：$O(n\ast \frac{s}{2})$
• 空间复杂度：$O(\frac{s}{2})$

class Solution:def canPartition(self, nums: List[int]) -> bool:s = sum(nums)if s % 2:return Falses //= 2f = [True] + [False] * ss2 = 0for i, x in enumerate(nums):s2 = min(s2 + x, s)for j in range(s2, x - 1, -1):f[j] = f[j] or f[j - x]if f[s]:return Truereturn False

---