知识点

LeetCode算法题

1. LeetCode算法题

   1. 学习

      1. 131.【分割回文串】

         解题思路：

         回溯算法，加动态规划优化。

         将 s 分割成一些子串，使每个子串都是 回文串 ，返回 s 所有可能的分割方案。因为涉及到具体的方案，并且求所有可能的方案，因此很有可能要用到dfs。

         我们可以先根据示例，看一下是否有什么分割的规律。根据示例，"aab"的方案是["aa","b"]和["a","a","b"]，可以看到假设将字符串s分割成n段，如果这n段都是回文串则就是一个分割方案。因此我们可以用dfs来做分割。

         因为要判断s的某个子串s[i..j]是否为回文，则可以使用动态规划对s进行预处理。

      2. 139.【单词拆分】

         解题思路：

         该题目可以转化为wordDict中的单词，不限制取用次数，是否可以构成字符串s，典型的完全背包问题。

      3. 152.【乘积最大子数组】

         解题思路：

         首先，按照惯性思考，我们会先考虑：根据「53. 最大子序和」的经验，我们定义以i为末尾的最大乘积为f(i) = max(f(i-1) * nums[i], nums[i])。

         但是，这种动态转移方程是错误的，没有考虑到nums[i]的正负性。

         正确做法参见LeetCode题目解答。