目录

动态规划

动态规划总结篇

dynamic programming, DP

什么是动态规划?

一句话解释:大事化小,小事化了
简单的解释:想办法将一个复杂的大问题拆成几个子问题,分别求解这些子问题,从而求出大问题的解。

什么样的题适合用DP求解?

具有以下两点特征的问题可以用DP求解:

  1. 重叠子问题(Overlapping Subproblems):有些子问题会被重复计算多次。
  2. 最优子结构(Optimal Substructure):问题的最优解可以从某个子问题的最优解中获得。

如何设计DP:

DP的核心是状态和状态转移方程:
状态:描述该问题的子问题的解,即根据子问题来定义状态。
状态转移方程:状态和状态之间的关系式。大部分情况下,某个状态只与它前面出现的状态有关,而独立于后面的状态(比如 斐波那契数列 f(n)=f(n-1)+f(n-2))。

动态规划的解题思路:

  1. 将原问题分解为子问题;
  2. 确定状态:状态不是随便定义的,一般定义完就要找到状态转移方程;
  3. 确定一些初始状态(边界状态)的值;
  4. 确定状态转移方程。

如果问题看起来是个动态规划问题,但是无法定义出状态,那么可以试着将问题规约到一个已知的 DP 问题。

两种设计思路:

  1. 默记法(从上到下)/ Memoization (Top Down):设置一个数组,当需要子问题的解时,先去这个数组中查找。如果此问题之前已经求过解,那么就直接返回该值,如果此问题之前并未求过解,那么就计算该值并把结果放入数组中,以备后用。
  2. 表格法(从下到上)/ Tabulation (Bottom Up):用迭代法建立一个表格,从该表格中返回所需的值。
    p.s.有时候会将默记法作为单独的一种方法。比如在 leetcode300的题解 中,会分为带记忆的递归(Recursion with Memoization)和动态规划(Dynamic Programming)方法,此时的DP方法特指表格法。

例题

从例题中学习才是最直接、有效的.

入门题

leetcode70爬楼梯:本题适合入门,题解分别阐释了两种设计思路(自上而下、自下而上)的实现。

普通题

leetcode300最长上升子序列

进阶题

leetcode44通配符匹配:本题属于二维动态规划,从这道题中可以直观的体会为什么自下而上的方法又叫表格法。
leetcode712两个字符串的最小ASCII删除和:本题属于二维动态规划,从这道题中可以直观的体会为什么自下而上的方法又叫表格法。