LeetCode刷题 | Day 4 分割等和子集（Partition Equal Subset Sum）自底向上动态规划

LeetCode刷题 | Day 4 分割等和子集（Partition Equal Subset Sum）自底向上动态规划

前言

LeetCode位置：416. 分割等和子集

日常刷题，维持手感，同步学习英语，刷题顺序参考B站UP@justyyuk的系列视频，感兴趣的点波关注。
学海无涯，大路千万，感恩此程，彼此真诚陪伴！

Ps：第一次刷到的道友留步，这里拉齐一下信息。文章主要记录视频中的主要内容，算法思路会按照个人理解，用伪代码+举例每步输出的方式呈现。代码部分会以Python和C++语法进行呈现。文章最后会总结一些英语词汇。OK，就啰嗦这么多，开始进步[干杯🐱‍👓]

一、题目概述

输入：nums列表
输出：bool值，表示原始列表是否存在和相等的两个子列表

PS：

1. 子序列 (Subsequence/Subset):

   • 子序列是通过从原始序列中删除一些或不删除任何元素且不改变剩余元素顺序而得到的序列。
   • 例子：对于序列 [1, 2, 3, 4]，[1, 3, 4] 和 [2, 4] 是子序列。
   • 注意：[1, 4, 3] 不是 子序列，因为顺序改变了。

2. 子列表 (Sublist)

   • 子列表是列表的连续部分，意味着元素必须是连续的。
   • 例子：对于列表 [1, 2, 3, 4]，[2, 3] 和 [1, 2, 3]是子列表。
   • 注意：[1, 3] 不是 子列表，因为它不是连续的。

3. 子数组 (Subarray):

   • 类似于子列表，子数组是数组的连续部分。
   • 例子：对于数组 [1, 2, 3, 4]，[2, 3] 和 [1, 2, 3] 是子数组。
   • 注意：[1, 3] 不是 子数组，因为它不是连续的。

• 在许多情况下，当数据结构是数组或列表时，“子列表”和“子数组”可以互换使用，但“子数组”一词专门用于数组。

二、解题方法

2.1 一维表格的自底向上动态规划

2.1.1 思路讲解

动态规划策略 ：
本题与昨天的是同一道题，不过这次采用自底向上（表格法）的动态规划策略。此处有两种方法，一种使用到一维表格，一种使用二维表格。

• 一维表格：用表格长度表示待达成目标，即数组和的一半（+1），表格内的值（True/False）表示子序列是否选择当前元素

  • 表格长度：表格 dp 的长度为 half + 1，其中 half 是数组总和的一半。这意味着我们试图判断是否存在一个子集，使其和为 0 到 half 之间的任何值。
  • 表格的值：dp[i] 是一个布尔值，表示是否存在一个子集，其和等于 i。
  • 初始化：dp[0] 被初始化为 True，因为和为 0 的子集总是存在的（空集）。其他位置被初始化为 False。
  • 状态转移：
  • 对于数组中的每一个元素 num，从后向前遍历 dp 数组（从 half 到 num），更新 dp 数组的值。
  • 更新规则为：dp[i] = dp[i] or dp[i - num]。这意味着如果存在一个子集和为 i - num，那么加上 num 后，和为 i 的子集也存在。

具体步骤：

1. 计算总和：total = sum(nums)，如果 total 是奇数，返回 False。
2. 计算目标子集和：half = total // 2。
3. 初始化 dp 数组：dp = [False for _ in range(half + 1)]，并设 dp[0] = True。
4. 遍历 nums 更新 dp 数组：
   • 对每个 j（来自 nums），从 half 到 j 更新 dp。
   • 如果 j <= i，则 dp[i] = dp[i] or dp[i - j]。
5. 返回 dp[half]，表示是否存在一个子集其和为 half。

2.1.2 伪代码 + 逐步输出示例

# 伪代码示例
函数 canPartition(nums):
    total = nums 的和
    如果 total 是奇数:
        返回 False
    half = total // 2
    dp = 长度为 half + 1 的布尔数组，所有元素初始化为 False
    dp[0] = True

    对于 nums 中的每一个 num:
        从 half 到 num 遍历 i:
            如果 dp[i - num] 为 True:
                dp[i] = True

    返回 dp[half]
    
# 逐步输出示例：
输入:[1, 2, 1]
初始化
•	total = 1 + 2 + 1 = 4
•	half = 4 // 2 = 2
•	dp = [True, False, False]（长度为 half + 1）
处理第一个元素 1
•	遍历 i 从 2 到 1（倒序）
	o	i = 2: dp[2] = dp[2] or dp[1] -> False or False = False
	o	i = 1: dp[1] = dp[1] or dp[0] -> False or True = True
•	更新后的 dp: [True, True, False]
处理第二个元素 2
•	遍历 i 从 2 到 2（倒序）
	o	i = 2: dp[2] = dp[2] or dp[0] -> False or True = True
•	更新后的 dp: [True, True, True]
处理第三个元素 1
•	遍历 i 从 2 到 1（倒序）
	o	i = 2: dp[2] = dp[2] or dp[1] -> True or True = True
	o	i = 1: dp[1] = dp[1] or dp[0] -> True or True = True
•	更新后的 dp: [True, True, True]
最终结果
•	返回 dp[half]