• 介绍
• 设计步骤
• 实现
• 两个例子
  • house robber(leetcode 198)
  • 使用最小花费爬楼梯(leetcode746)
• 参考

介绍

动态规划（Dynamic programming）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
适用于满足有重叠子问题（overlap sub-problem）、无后效性、具有最优子结构（optimal sub-structure）的问题求解。
重叠子问题：一个子问题在不同阶段的决策中可能被多次用到。
无后效性：某状态以后的过程不会影响以前的状态，只与当前状态有关。
最优子结构:问题的最优解所包含的子问题的解也是最优的。

例如斐波那契数列问题，递归解法时间复杂度 $O(2^n)$，添加记忆后复杂度下降到O(n)，

设计步骤

动态规划解决的问题通常是多阶段的决策问题，通过一个决策序列完成从初始状态到结束状态的转移，通常我们求解的就是最优的决策序列。动态规划的一般设计模式主要有以下几个步骤：
1. 划分阶段
将问题划分为有序的多个阶段。
2. 确定状态和状态变量
将问题的不同阶段的情况表示出来，状态的选择满足无后效性。
3. 状态转移方程
状态转移方程是动态规划的关键，状态转移是根据上一阶段的状态和决策导出本阶段的状态，而状态转移方程常常是根据相邻阶段状态之间的关系来决定的。
4. 边界条件
状态转移方程是一个递推式，需要一个终止条件，通常来说边界条件也决定了程序中循环的出口。

实现

设计完解决问题的阶段、状态、转移方程,就可以通过状态转移的递推关系来解决问题，由于重叠子问题的存在，通常将子问题的解保存在表中以减少计算。使用状态和决策建立决策表，整个求解过程就是填写表格，得到一个最优的决策表。

两个例子

house robber(leetcode 198)

问题描述：给定一个数组，在不选取相邻数值的条件下输出能选取数值之和的最大值。
[1,2,3,1]->[1,3]->4
有序地处理数组，在处理每一个数值时都是一个不同的阶段；状态即为已选取的数值之和；决策为选或不选(0-1)。
转移方程如下，v为给定数组

$f(n)= \begin{cases} f(n-1), & \text {不选} \\\\ v[n]+f(n-2), & \text {选} \end{cases}$

边界条件由递推式可得，数组长度小于二时另行处理，或求得$f(n)$时完成递推，最优决策由在每个决策分支取max取得。

代码：

def rob(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if len(nums)==0:
        return 0
    elif len(nums)==1:
        return nums[0]
    opt = [0]*len(nums)
    opt[0] = nums[0]
    opt[1] = max(nums[0],nums[1])
    for i in range(2,len(nums)):
        A = opt[i-2]+nums[i]
        B = opt[i-1]
        opt[i] = max(A,B)
    return opt[len(nums)-1]

使用最小花费爬楼梯(leetcode746)

问题描述：数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 costi。每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。需要找到达到楼层顶部的最低花费。可以选择从索引为 0 或 1 的元素作为初始阶梯。
同样的，有序地处理数组，在处理每一个数值时都是一个不同的阶段；状态即为已选取的数值之和；决策为爬一层或爬两层。
转移方程如下，v为给定数组

$f(n)= \begin{cases} v[n-1]+f(n-1), & \text {爬一层} \\\\ v[n-2]+f(n-2), & \text{爬两层} \end{cases}$

边界条件由递推式可得，数组长度小于二时另行处理，或求得$f(n)$时完成递推，最优决策由在每个决策分支取min取得。
代码：

def minCostClimbingStairs(self, cost):
        """
        :type cost: List[int]
        :rtype: int
        """
        l = len(cost)
        if l == 0:
            return 0
        elif l == 1:
            return cost[0]
        elif l == 2:
            return min(cost[0],cost[1])
        opt = [0]*(l+1)
        opt[0] = 0
        opt[1] = 0
        for i in range(2,l+1):
            opt[i] = min(opt[i-1]+cost[i-1],opt[i-2]+cost[i-2])
        return opt[l]

每个阶段只有一个状态->递推；
每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心；
每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索；
每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划。zhihu

参考

https://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741374.html