从青蛙跳台阶说起

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

一只青蛙一次可以跳上 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。称之为边界条件。
两部分具备之后，很容易可以写出代码：

1
2
3
4
5
6

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

重叠子问题

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

1
2
3
4
5
6
7
8
9

                       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)

记忆化搜索

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

1
2
3
4
5
6
7
8

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 的内置函数：

1
2
3
4
5
6
7
8

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 的情况，然后依次向上计算，每次计算都存表即可。

1
2
3
4
5
6
7
8
9
10
11

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 是一维的，所以称之为一维动态规划。

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

1
2
3
4
5
6
7
8
9

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

动态规划和递归

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

动态规划和分治

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

动态规划和贪心

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

一维动态规划 Leetcode 题目

• Climbing Stairs
• Decode Ways
• Unique Binary Search Trees
• Maximum Subarray
• Maximum Product Subarray
• Best Time to Buy and Sell Stock

二维动态规划