动态规划

1,618 阅读4分钟

从青蛙跳台阶说起

这个问题和斐波纳契数字问题是一样的。题目描述如下:

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

考虑递归

首先用递归的思路来考虑。递归是倒着分析的。

假如只差一步就能走完整个台阶,要分为几种情况?因为每一步能走一级或者两级台阶,所以有如下两种情况:

  • 最后一步走2级台阶,也就是从n-2级到n级
  • 最后一步走1级台阶,也就是从n-1级到n级

所以第n步的走法由两种方法的和构成。如果定义F(n)为第n步的走法,那么F(n)=F(n-1)+F(n-2)。这个公式称之为递推公式。 当只有1级台阶和2级台阶时走法很明显,即F(1)=1、F(2)=2。称之为边界条件。 两部分具备之后,很容易可以写出代码:

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

验证的时候会发现一个问题,如果n比较大,那么会导致计算机栈的溢出,即便是n=100的时候也需要相当长的计算时间。那么问题出在哪里呢?

重叠子问题

我们不妨把上面的递归式子以树的形式表示出来,结果如下:

                          F(5)
                     /             \
                F(4)                  F(3)
             /      \                /     \
         F(3)       F(2)         F(2)     F(1)
        /     \     /    \       /    \
      F(2)   F(1) F(1)  F(0)  F(1)   F(0)
     /    \
   F(1)  F(0)

可以看到这其中有很多重复求解部分,称之为重叠子问题。 一种想到的改进方法是我们可不可以把递归计算中某些计算过的结果存起来,来避免这个问题。下面介绍记忆化搜索和LRU 缓存策略实现这种改进方法。

记忆化搜索

记忆化搜索的思路如下:每当我们需要解决子问题时,我们首先查找查找表。如果预先计算的值存在,那么我们返回该值,否则我们计算值,并将结果放在查找表中,以便以后可以重复使用。

lookup = [0,1,2]+[0]*100

def fun(n):

    if lookup[n] == 0:
        lookup[n] = fun(n-1)+fun(n-2)

    return lookup[n]

LRU缓存

LRU(Least recently used,最近最少使用),其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。对于本题目,如果是高频出现的计算函数的结果会被放到缓存中,再次出现只需要在缓存中读取即可,和记忆化搜索类似。python有LRU的内置函数:

from functools import lru_cache
@lru_cache(None)
def fun(n):
    if n==2:
        return 2
    if n==1:
        return 1
    return fun(n-1)+fun(n-2)

有了上述方法,n=100已经可以计算了。但是虽然有这两个缓解的方法,但是仍存在问题。当n=1000的时候仍然会存在堆栈溢出的问题。

一维动态规划

上面的思考都是基于递归的,即自顶而下的计算方法。如果我们换个思路,自底而上呢?

其实和上面的记忆化搜索很像了。首选记录n=1的情况和n=2的情况,然后依次向上计算,每次计算都存表即可。

N = 10

dp  = [0]*(N+1)
dp[1] = 1
dp[2] = 2

def fun(n):
    for i in range(n+1):
        if i>2:
            dp[i] = dp[i-1] + dp[i-2]
    return dp[-1]    

这种方法存的表称之为DP Table,这种解决思路称之为动态规划。本题目的DP Table是一维的,所以称之为一维动态规划。

当然针对这个问题,对空间还可以进一步优化:

def fun(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    pre,prepre = 2,1
    for i in range(n - 2):
         prepre, pre = pre, pre + prepre
    return pre

动态规划和递归

上面我们已经见到过了:递归采用的是“由上而下”的解题策略并带有可能的”子问题“重复调用,时间复杂度自然高,而且容易造成堆栈的溢出。

例如求解Fib数列就包含重复子问题,此时考虑动态规划

但是求解归并排序的时候每个子问题都是独立的,因此考虑分治递归

动态规划和分治

两者的区别在于:动态规划的下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解。

动态规划和贪心

贪心算法每走一步都是不可撤回的,而动态规划是在一个问题的多种策略中寻找最优策略,所以动态规划中前一种策略可能会被后一种策略推翻。

一维动态规划Leetcode题目