for english version: https://dev.to/yunshu67/dynammic-programming-notes-8do#aaa

动态规划笔记 dynammic programming notes

Table of contents


 

动态规划 Dynamic Programming

动态规划(英语:Dynamic programming,简称DP)是一种在数学管理科学计算机科学经济学生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有重叠子问题[1]最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再根据子问题的解以得出原问题的解。

通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量:一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。


解决动态规划问题的一般流程

  1. 确定 state

    即区分原问题和子问题的量,一般为 dp function的自变量或dp array的index e.g 原问题为dp(n), 子问题为dp(n-1)

  2. 确定 base state case

    一般为state=0的情况, 即dp(0)dp[0]

  3. 确定 strategy

    即原问题分解成子问题*的不同方法 e.g.

  4. 定义 dp functiondp array (状态转移方程)

    根据strategy列出方程

    • 自顶向下: dp function

      • 可能会重复计算某些子问题 => 用hash table储存已经计算了的子问题
      • 时间复杂度,空间复杂度都很高
    • 自底向上

      • Time complexity O(n), space complexity O(n)

      • Optimisation: 若dp[n]只与dp[n-1], dp[n-2]有关,则可以用滚动数组的思想优化

        Space complexity: O(1)

Reference:

知乎


Examples

85. Maximal Rectangle

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example 1:

img

动态规划思想:

IMG_0685

代码: