08｜子数组问题：从解决动归问题套路到实践解题思路
什么是子数组问题？
荧光笔
直线
曲线- 深入了解
- 翻译
- 解释
- 总结
本文介绍了动态规划算法在解决子数组问题中的应用。首先，文章从动态规划的基本概念出发，明确了子数组问题的特点和解决方法。以回文子串个数问题为例，详细分析了动态规划在解决子数组问题时的应用，并给出了具体的代码实现。文章强调了动态规划问题的分析方法，包括重叠子问题、无后效性和最优子结构，并通过示例和图示展示了动态规划在解决子数组问题时的思路和操作步骤。另外，文章还介绍了求解最大子数组之和的问题，从初始化状态到状态转移方程的设计，详细分析了动态规划在该问题中的应用。总的来说，本文通过清晰的逻辑结构和详细的分析，为读者提供了解决子数组问题的思路和方法，对于想要深入了解动态规划算法的读者具有很高的参考价值。 文章还介绍了对动态规划问题的空间复杂度优化，以及如何根据状态的依赖关系进一步缩减备忘录的空间，进一步降低空间复杂度。通过本课的两个子数组问题，读者可以认识到子数组这类动态规划问题的形式，了解如何寻找状态和子问题、构建状态转移方程，并对其进行优化。在后续的课程中，读者还会看到更复杂的子数组问题。最后，读者被引导思考如何区分使用滑动窗口等传统算法来解决子数组问题，以及与动态规划问题之间的区别。 总的来说，本文内容详实，逻辑清晰，对动态规划算法在解决子数组问题中的应用进行了全面而深入的阐述，对读者具有很高的参考价值。
《动态规划面试宝典》，新⼈⾸单¥59
全部留言(11)
- 最新
- 精选
- Paul Shan子串问题能用动态规划法的最优解往往是从一个长度为0或1的子串一步一步推导出来的，约束往往在子串的两端。滑动窗口的使用的场合，最优结果很多不能一步一步推导出来，约束往往是全局层面的，例如某个字符出现的次数等。
作者回复: 没错，滑动窗口的使用场合，最优解很可能不能一步一步推导出来。 滑动窗口算法非常简单，就是维护一个窗口，不断滑动并更新答案。 但对于咱们在本课中讲到的“最大子数组之和”这个问题来说，原问题的输入是包含负数的！所以回到上面那个叙述：当窗口扩大的时候可能遇到负数，窗口中的值可能增加和减少，这种不确定性就已经限制了我们去使用滑动窗口：我们不知道什么时候该收缩左侧窗口，也就无法求出原问题的答案。
2020-09-3010 
廖熊猫最大子数组问题中， “DP[i] 表示的是以 i 为结束位置的最大子数组之和” 我觉得这个说法不是特别妥当，某些情况下，DP[i]并不是以i为结束位置的最大子数组之和。 [-2, 1, 1, 4, -3, 3, -5, 1, 2]这个问题中， DP备忘录打印出来为 [-2, 1, 2, 6, 3, 6, 1, 2, 4]，我觉得这个备忘录更像是以i为结束位置，且不小于i的子数组的和。作者回复: 这里DP[i]表示的的确是以i为结束位置的最大子数组之和，也就是说这个子数组一定要包含DP[i]这个元素，和你说的“以i为结束位置，且不小于i的子数组的和”是一样的。
2020-10-031
coder“最长回文子串问题属于动态规划当中的求方案个数的问题” 应该是 “最大回文子串个数”。作者回复: 已修正，感谢反馈！
2023-07-21归属地：北京
Abner老师好！最大子数组和那里，为什么是DP(i,j)，j用在哪里了呢？作者回复: 金柳颀 13:32:46 这个问题的原始的问题是DP(i,j) 意思是从数组中取第i个位置到第j个位置中最大的子数组和 只不过因为我们的问题是求整个数组的最值，所以起始位置必定是0，所以最后简化成DP(i) 表示从第0个位置到第i个位置中最大的子数组和 最后并没有使用j
2022-05-27
绘世浮夸 つ多次刷之后终于有点感觉了，谢谢老师作者回复: 赞～给你顶一顶，让更多人看到 :heart:
2022-03-02- CD第一遍看，感觉天书 第二遍看 有点感觉 第三遍看，茅塞顿开
作者回复: DP 问题的解题思路和问题类型就那么几种，也就是说能用DP 解决的算法问题或工程问题也是有限的。因此，以不变应万变，是可以考虑的方法呢。
2022-01-26 - CD对于这类子数组问题，我们需要重新定义备忘录的含义，即 DP[i] 表示的是以 i 为结束位置的最大子数组之和 没说为什么这样定义是可以的吗
作者回复: 这个就是经验总结。具体来说就是这样的确可以解决这些问题，没有严格的证明。
2021-12-21 
Jonathan子数组和子序列是两种不同类型的问题作者回复: 是的，这是两类不同的问题，思路也不完全一致。
2021-04-12
猫头鹰爱拿铁leetcode 53题也就是最大子数组和的问题，每次做每次错，这道题一定要想清楚dp[i]定义的是包括i的子数组和，不然按照做题的直觉总会想成是0...i的最优解，这样就错了。作者回复: 是的，这个是这道题的关键点，思路一定不能错。
2020-11-30
yhh"每次遍历时，首先确定是需要开始一个新的连续子数组，还是扩展之前的连续子数组。如果当前位置的元素大于前面最优解子数组与当前元素之和，说明应该以当前位置开始一个新的子数组；否则说明当前元素应该是前一个最优解的扩展，得到一个更大的连续子数组" 看不太懂为什么是这样的作者回复: 我们分两种情况讨论： 1. 如果以i-1为结尾的最大子数组之和为负数，那么以i为结尾的最大子数组之和肯定是自己，也就是一个新的子数组，这个子数组只有第i个元素。 2. 如果以i-1为结尾的最大子数组之和大于0，那么以i为结尾的最大子数组之和肯定是前面的子数组之和加上当前数字，也就是把第i个元素加入以第i-1个元素为结尾的数组里去。 这样描述应该就简单清晰很多了。
2020-11-15
