知识点

LeetCode算法题

1. LeetCode算法题

   1. 复习

      1. 72.【编辑距离】

         解题思路：

         两个字符串动态规划问题，一般都需要两个指针，分别指向两个字符串的末尾，然后开始解决问题。

   2. 学习

      1. 64.【最小路径和】

         解题思路：

         一般矩阵中求最优化问题，都需要使用动态规划技巧。

         先利用递归思路，写出递归函数，穷举出结果。然后利用备忘录，处理重叠子问题。这就是标准的自顶向下的动态规划了。

         当然，我们也可以利用迭代，写出自底向上的动态规划解法。状态转移方程是不变的，因此比较容易写出。

      2. 931.【下降路径最小和】

      3. 494.【目标和】（很有意思）

         解题思路：

         首先，想到可以通过回溯算法解题。回溯算法时间复杂度为O(2^N)。

         然后，想到可以通过备忘录消除重叠子问题。相当于回溯算法的剪枝，最坏情况下，时间复杂度仍然为O(2^N)

         我们转化一下问题：把 nums 划分成两个子集 A 和 B，分别代表分配 + 的数和分配 - 的数，那么他们和 target 的关系为sum(A) - sum(B) == target。转化一下变为sum(A) == target + sum(B)，再转换一下sum(A) + sum(A) = target + sum(nums)，最终转化为sum(A) == (target + sum(nums)) / 2。

         因此，该问题就变成了，nums中有几个子集A满足sum(A) == (target + sum(nums)) / 2。

         子集划分问题是经典的背包问题，因此该题目又变为了：nums中的元素，如果每个只能取一次，装满(target + sum(nums)) / 2有几种装法。