概念

动态规划的英文名称 dynamic programming，简称为 DP，算法导论对动态规划的定义：

A dynamic-programming algorithm solves each subproblem just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every time it solves each subproblem.

动态规划算法仅用一次解决每一个子问题，并将解保存在表中，因此避免每次求解子问题时的重复计算。

爬楼梯，初步领悟 DP

Climbing Stairs 问题描述如下：每次只能爬 1 步 或 2 步，问有多少种爬到楼顶的方法，假设一共有 n 层。

分析

假设爬到顶层一共有 f(n) 种，则爬到第 n−1 层一共有 f(n−1) 种，爬到第 n−2 层一共有 f(n−2) 种，那么，f(n)、f(n−1)、f(n−2) 之间有什么关系？

如果只经过 1 步，爬到第 n 层，一共有两种爬法：

1. 从第 n−2 层爬 2 步到第 n 层；
2. 从第 n−1 层爬 1 步到第 n 层。

因此，爬到第 n 层的方法一共有：

f(n) = f(n−2) + f(n−1)

至此，找到 DP 最关键的递推公式。

将求解到第 n 层的方法 f(n) 转化为分别求解到第 n−1 层和到 n−2 层的方法。

依次递归，直到 n 等于 2 或 1，且知道 f(2)=2，f(1)=1。

递归版

根据上述思路，Python 代码实现：

def climb_stairs(n):
    if n==1:
        return 1;
    if n==2:
        return 2;
    return climb_stairs(n-1) + climb_stairs(n-2)

这种求解算法的时间复杂度是 O(2^n)，指数级的时间复杂度根据 Day42 介绍是很不理想的。

空间换取时间

没有免费的午餐，要想获得时间性能，很可能意味着就会牺牲其他一些东西。动态规划法通过牺牲空间换取时间效率，这被称作 time-memory trade-off。

所谓的空间对于计算机模型而言便是申请一块内存空间。

优化版本 V1.1：

def climb_stairs(n):
    dp = [1,2]
    for i in range(2,n):
        dp.append(dp[i-1] + dp[i-2])
    return dp[n-1]

这个算法的时间复杂度为 O(n)，空间复杂度为 O(n)。与版本 1.0 相比时间复杂度上已经产生质的飞跃。

但是，还有没有优化空间？

注意观察，上述 V1.1 代码，每次遍历都会增加 1 个元素到 DP 中。

然而这真的有必要吗？其实，只需要记忆 f(n−1) 和 f(n−2) 两个值就行。为此代码进一步优化为：优化版本 V1.2。

def climb_stairs(n):
    dp = [1,2]
    for i in range(2,n): 
        tmp, dp[1] = dp[1], dp[0] + dp[1]
        dp[0] = tmp
    return dp[1] if n > 1 else 1

机器人行走路径

下面是一道经典 LeetCode 面试题，计算从 start 到 finish 的最短路径，设机器人只能沿向下或向右方向行走。这道题的形象化表示如下所示：

分析问题

要想从 start 点到 finish 点，那么，必然经过 h1 或 h2 点，如下图所示：

所以，问题转化为：求 start 点到 h1 点，或到 h2 点的路径中的较小者，这相当于将问题域变小 1，递归下去直到问题域变为 1 个点。

总结递归方程，分四种情况。

情况一：

情况二：

情况三：

情况四：

其中，

• dp[i,j]：到第 i 行和第 j 列的最短距离；
• grid[i,j]：网格的长度。

注意每个网格长度可能不等，上面两幅图只是示意图。根据状态转移方程，使用 Python 实现。如下为输入的网格，每一个元素代表网格的长度。

grid = [[1,3,1],[1,5,1],[4,2,1]]

Python 代码实现

def min_path_sum(grid):
        m, n = len(grid), len(grid[0])
        dp = [[] for _ in range(m) ] #记录到当前点的最短距离
        #边界情况
        dp[0].append(grid[0][0])

        for i in range(1,m):
            dp[i].append(dp[i-1][0] + grid[i][0])
        for j in range(1,n):
            dp[0].append(dp[0][j-1] + grid[0][j])

        # 迭代方程1
        for i in range(1,m):
            for j in range(1,n):
                dp[i].append(min(dp[i-1][j],dp[i][j-1]) + grid[i][j])

        return dp[m - 1][n - 1]

dp = [[] for _ in range(m) ]

记录到当前点的最短距离，这也是空间换取时间的经典 DP 风格 （time-memory trade-off）。

DP 通用条件

面对一个问题如何知道这个问题是否能用 DP 求解？

首先从实际问题具有的特征入手，如果符合动态规划的主要条件，那么就可以尝试用动态规划求解。

一般地，能用动态规划求解的问题具有 2 个核心特征：

1. optimal-substructure property：最优化的子结构属性
2. overlapping subproblems：重叠的子问题集

最优化子结构属性是指如果一个问题的最优解包含在一系列的子问题集的最优解中，那么它便具有最优化的子结构属性。

拿爬楼梯的例子，如果想求解爬到第 i 层楼梯的所有方法，相当于求解以下子问题（subproblem）：

求爬到第 i-1 层的所有方法和爬到第 i-2 层的所有方法两者的累计和，那么爬到第 i-1 层的所有方法，又是一个子问题，相对于爬到第 i 层的方法便被称为 subsubproblem。这个爬楼梯问题非常明显地具有最优化的子结构属性。

重叠的子问题算法导论的解释：

When a recursive algorithm revisits the same problem repeatedly, we say that the optimization problem has overlapping subproblems.

意思是说，当一个递归算法再次访问同一个问题时，这种事会出现一遍又一遍，我们说这个最优化问题有重叠的子问题集。

如果我们分别求出爬到第 i-1、第 i-2 层的所有方法，那么在求解爬到第 i 层的所有方法时，我们还得去解决爬到第 i-1、第 i-2 层的所有方法，这就是重叠的子问题。

如果记录下爬到第 i-1、第 i-2 层的所有方法，然后使用时直接 look up.

以上便是两个动态规划问题常常具备的特征，如果待解决的问题满足这两个特征，便值得使用动态规划技术尝试去求求解。

深入 DP

先看原题，摘自 LeetCode 官网：

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. For "(()", the longest valid parentheses substring is "()", which has length = 2. Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

题目的意思是求出有效括号的长度的最大值，举几个例子：

(()   有效长度为2 
)()()) 有效长度为4 
((()()()) 有效长度为8

初步分析

看到这个问题，首先要想给定一个字符串，怎么判断这个字符串是否是有效的字符串括号？

想到借助栈，如果是 ( 将之推到栈中；如果是 )：

• 栈顶如果是 (，则表明找到一对有效的组合并出栈 (；
• 如果不是 (，说明这个不是有效字符括号串，或者栈为空，进来一个 )，也表明不是有效的字符串。

找到判断一个字符串是否是有效的方法后，可以穷举这个字符串括号的所有子字符串，这是一个 O(n^3) 时间复杂度的算法。

版本 1.0

def longest_valid_parentheses(self, s):
        def is_valid(sub):
            sta = []
            for it in sub:
                if it == '(':sta.append('(')
                elif len(sta) > 0 and sta[-1] == '(':sta.pop()
                else: return False
            return len(sta)==0
        i= 0
        max_len = 0
        while i < len(s):
            j = i + 2
            while j <= len(s):
                if is_valid(s[i:j]):
                    max_len = max(max_len, j-i)
                j += 2  
            i += 1
        return max_len  

上面解法尽管时间复杂度 O(n^3)，但是对于判断字符串是否是有效字符仍有借鉴之处。基于此，借助动态规划技术详细分析。

1. 如果一个括号串的结尾是 (，那么这个括号串一定不是有效的串；有效的括号串一定得以 ) 结尾才行。

接下来，最重要的一个变量定义：

dp[i]，表示以索引 i 结尾的字符串的最长长度。此变量是应用 DP 求解的关键一步。DP 适用条件的思想：原问题的最优解一定是由子问题的最优解组成的。

因为上文提到过，有效字符串一定得以 ) 结尾，并且研究两个连续相邻的字符，需要讨论两种情况，即：

(   ) 
)   )

详细讨论如下。

2. 如果 str[i] = ')'，并且 str[i-1] = '('，比如 ...( ) ( )，在这种情况下的状态转换方程为

3. 如果 str[i] = ')'，并且 str[i-1] = ')'，比如 ...) )，如果再满足 str[ i - dp[i-1] - 1] = '('，比如 .....( ( ) ( ) )，这种情况的状态转化方程为：

这种情况不是很好理解，请参考下图理解，可以看到索引 i 此时等于 7：

至此这个问题，借助动态规划的思想，通过找到状态的转移方程，便找到问题的解，状态转移公式由以上情况组成。

版本 2.0

def longest_valid_parentheses(s):
    maxlen = 0
    dp = [0 for i in range(len(s))]
    for i in range(1,len(s)):
        if s[i] == ')': #这是第一个大条件
            if s[i-1] == '(':     #情况1
                dp[i] = dp[i-2]+2 if i>=2 else 2 
            elif i-dp[i-1] > 0 and s[i-dp[i-1]-1] == '(': #情况2
                tmp = dp[i-dp[i-1]-2] if i-dp[i-1]>=2 else 0
                dp[i] = dp[i-1] + 2 + tmp
            maxlen = max(maxlen, dp[i]); 
    return maxlen

版本 2.0 的时间复杂度变为 O(n)。

小结

动态规划求解问题的关键，确定状态转移方程，该方程包含着子问题的解。原问题的最优解是由子问题的最优解组成的。

DP 求解确保得到最佳效果，需要保证对子问题求解有且只有一次，通过记忆功能（memory function），维护一个自底向上、DP 算法使用的表格来实现。