2021 5.1~5.10

  • 线段树：在对数时间内解决多种范围查询问题（基于数组的线段树，实现了创建线段树，更新线段树，区域查询等操作）。
  • leetcode 53：最大子序和。（一维 dp 问题）
  • leetcode 152：乘积最大子数组。（一维 dp 问题，但是需要借助两个一维 dp 数组保存状态）
  • leetcode 300：最长递增子序列。（一维 dp 问题，核心思想为在原有的子序列后面尝试拼接，以此推出新状态）
  • leetcode 307 区域和检索。（线段树的应用，以 O(logN) 实现区域和的查询，以 O(logN) 实现线段树的更新）
  • leetcode 354：俄罗斯套娃信封问题。（一维 dp 问题，处理技巧：先对信封宽带 w 进行排序(固定这一维度)，然后对信封高度 h 进行最长递增子序列问题的求解）
  • leetcode 673：最大递增子序列的个数。（一维 dp 问题，300的变形，需要在更新 dp 数组的过程中，顺带记录最大递增子序列的个数）
  • leetcode 最大子矩阵和。（二维 dp 问题，可以进行状态压缩，需要从 二维 dp 的暴力解法推导而出）
  • leetcode 363 矩阵区域不超过 K 的最大数值和。（二维 dp 问题，状态压缩，可以利用朴素二维前缀和求解，状态压缩解法暂无掌握）

5.11~5.16

  • leetcode 198：打家劫舍。dfs or 二维dp(也可以用一维dp)。
  • leetcode 918：环形数组最大和。将问题分为组成环形数组和不组成环形数组。不组成环形数组的情况用连续子数组最大和方法求解。组成环形数组的情况求解连续子数组最小和。将问题转化为 子数组最大和 = 数组总和 - 子数组最小和。