什么是动态规划

其实就是动态递推，本质上是 递归+记忆化,就拿斐波那契数列来说，其组成形式如 0，1，1，2，3，5...,后一项等于前两项之和。即 n<=1时为 f(n)=n，否则 f(n)=f(n-1)+f(n-2),这就是递推公式，递推只需要关注相邻状态，且自底向下推导。

1.递归方案一

def fib(n):
    return n if n<=1 else fib(n-1)+fib(n-2)

这个方案的算法复杂度是O(2^n),可以想象的到是不断的递归压栈形成二叉树结构，因为里面会重复算 fib(2),fib(3),fib(4),fib(1),fib(0),显然算法上不是最优的。

2.递归方案二

def fib(n):
    cache=[None]*(n+1)
    cache[0]=0
    cache[1]=1
    i=2
    while i<=n:
       cache[i]=cache[i-1]+cache[i-2]
        i+=1
    return cache[n]

方案二我们将每次计算的结果都保存至一个缓存变量，这样就减少了重复运算的次数。

利用状态转移方程

有一个m行n列的棋盘，一只猫需要从棋盘的最左上角格子走到最右下角格子，且只能横向或竖向移动，棋盘中间有的格子分布有石头，代表此路不通，让我们计算出猫的路径条数。

思路：我们可以从起点格子或终点格子考虑，起点格子的路径等于与其相邻的格子的路径之和，与终点相邻的格子路径分别为1，加起来就是相邻斜线格子的路径数。所以我们递推出状态转移方程：opt[i,j]=opt[i-1,j]+opt[i,j-1]，起始点的路径数就是结果值。

def count_of_paths(m, n, list):
    opt = [([0] * n) for _ in range(m)]
    for i in range(m):
        for j in range(n):
            if list[i][j] == 'E':
                opt[0][j]=1
                opt[i][0]=1
                opt[i][j] = opt[i-1][j] + opt[i][j-1]
            else:
                opt[i][j] = 0
    return opt[-1][-1]

# 构建以终点为原点的坐标系，E代表空地，S代表有石头，C代表终点位置
testdata = [['C', 'E', 'E', 'E', 'E', 'E', 'E', 'E'],
            ['E', 'E', 'S', 'E', 'E', 'E', 'S', 'E']
    , ['E', 'S', 'E', 'S', 'S', 'E', 'E', 'E']
    , ['S', 'E', 'E', 'E', 'E', 'S', 'E', 'E']
    , ['E', 'E', 'S', 'E', 'E', 'S', 'E', 'S']
    , ['E', 'E', 'E', 'S', 'E', 'E', 'E', 'E']
    , ['E', 'S', 'E', 'E', 'E', 'S', 'E', 'E']
    , ['E', 'E', 'E', 'E', 'E', 'E', 'E', 'E']]

print(count_of_paths(8, 8, testdata))

这里我们还可以扩展取任意一点的路径数，即找到最优子结构。

动态规划 vs 回溯 vs 贪心

回溯（递归）：傻傻的穷举，重复计算
贪心：关注眼前的利益，永远局部最优
动态规划：集前两者之大成，记录局部最优子结构/多种记录值

这有点像我们追求的极致人生，要么每天重复自己的工作生活，傻傻呆在舒适区跳不出来；要么只看眼前利益，功利心切，恨不能走捷径秒变高富帅；但现实往往打脸，反而随着年纪的增长，会不断复盘迭代人生轨迹，不断调整适应，关注长期发展，不急躁，静下心来反而会得到最好的结果。

动态规划的应用

1.爬楼梯，假设有3阶楼梯，可以每次走1阶，也可以每次走2阶，走到顶部看看有多少种方法。

两种思路：一种是回溯递归,类似斐波那契数列求解；一种是动态规划,DP状态的定义部分即f(n)为到第n阶的走法个数，DP方程为f(n)=f(n-1)+f(n-2);f(0)=f(1)=1,这里的算法复杂度O(n)。

方案一

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        cache=[None]*(n+1)
        cache[0]=1
        cache[1]=1
        i=2
        while i<=n:
            cache[i]=cache[i-1]+cache[i-2]
            i+=1
        return cache[n]

当然用 Python 也可以这样写，但感觉可读性没有上面好。

方案二

class Solution(object):
    def climbStairs(self, n):
        x,y=1,1
        for _ in range(1,n):
            x,y=y,x+y
        return y

2.给出一个三角形，求自顶向下的最小路径和，如[[2],[3,4],[6,5,7],[4,1,8,3]],其自顶向下路径最小和为11。即2+3+5+1=11。思路：每到一层选定一个数字，到下一层只能选择跟其相邻的数字，我们要做动态规划的策略就是自底向下，跟需求反着分析，找到DP的状态定义以及状态转换方程。

TODO:方案稍后添加….