一维DP

题目列表

  • leetcode

  • Climbing Stairs

  • Decode Ways
  • Unique Binary Search Trees
  • Maximum Subarray
  • Maximum Product Subarray
  • Best Time to Buy and Sell Stock

什么情况下可能使用DP

  • 求 max/min
  • yes/no 求能否达到
  • count(*) 求数量

什么情况下可能不是DP

问题描述

动态规划就是利用存储历史信息来减少重复计算，从而降低时间复杂度，用空间换时间的算法思路

动态规划的基本思路

  1. state，也就是dp表示的状态，确定递推量具体含义，也会定下维度
  2. function， 连接方程，这是最难的地方
  3. init, 初始化状态
  4. result, 最后的result是哪一个状态

常见优化：

有的时候对于历史信息的要求仅限于前面几步，就可以减少存储的空间

类型1

题目

  • climbing chairs
  • jump game
  • decode ways
  • unique binary search trees

思路

类型1比较简单，按照general思路来想，找到递推式

类型2 global, local

题目

  • maximum subarray
  • maximum product subarray
  • best time to but and sell stock

思路

当看到一个题目，对于要求的结果可以选择包含还是不包含当前value[i]时，就可以往这个方向想了

这种类型的题目要维护两个DP：

  • global 全局最优 （到目前为止最好的结果，不一定包含当前值）
  • local局部最优 （包含当前值的最优结果）

递推式： 根据local和global还有当前value[i]的关系，找出他们的递推式，最终结果是看global

题目

  • submatrix sum

这道题跟subarray sum类似，但是是二维的，但是如果我们将行的上下边界固定，将每一列的和当做一个元素的话，就和array的问题类似。

！pic