【数据结构和算法】三、动态规划原理讲解与实战演练

爬楼梯问题: . - 力扣(LeetCode)

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

示例 1:

输入:n = 2
输出:2
解释:有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2:

输入:n = 3
输出:3
解释:有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示:

  • 1 <= n <= 45

(1)解题思路1:

暴力求解,排列所有1,2的组合。

寻找总和为n的,不同数字长度的组合。

from itertools import product

def climbStairs(n):
    pms = []
    for rep in range(1,n+1):
        permutations = list(product([1,2],repeat=rep))
        for pm in permutations:
            if sum(pm) == n:
                pms.append(pm)
    return len(pms)

itertools是python为高效循环而创建迭代器的函数库 。product就是一个笛卡尔积(嵌套for循环)功能实现的函数。

  • 时间复杂度O(n^3)
  • 空间复杂度O(n)

(2)解题思路2:

问题寻找的是爬楼梯的方法数量,而不是具体统计每次走几阶。

所以问题关注的是每次爬1阶、爬2阶两种走法的组合上。

假设n=3,可以直接排列一下相应的组合

3 = 1 + 1 + 1
3 = 2 + 1
3 = 1 + 2

简单直观,但我们要寻找的爬楼梯的规律。似乎还没有发现,继续增加n的数量~

当n=4:

4 = 1 + 1 + 1 + 1
4 = 2 + 1 + 1
4 = 1 + 2 + 1

4 = 1 + 1 + 2
4 = 2 + 2

当n=5时:

5 = 1 + 1 + 1 + 1 + 1
5 = 2 + 1 + 1 + 1
5 = 1 + 2 + 1 + 1

5 = 1 + 1 + 2 + 1
5 = 2 + 2 + 1

5 = 1 + 1 + 1 + 2
5 = 2 + 1 + 2
5 = 1 + 2 + 2

        排列组合的方式,让我们似乎观察到了数值的规律。那就是n阶的走法,包含了n-1阶和n-2阶的走法。且 n阶的走法 = (n-1)阶走法 + (n-2)阶走法

简单的循环遍历就可以完成走法的累加:

n = 5
n1,n2 = 1,2  # n=1和n=2情况下的走法
res = 0
for i in range(3, n+1):  # 从n=3时开始,直到n
    res = n1 + n2
    n1 = n2
    n2 = res
print(res)

测试下n=6,结果(n-1) + (n-2) = 8 + 5 = 13

还可以转换为递归写法

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

至此,就是暴力算法的解题思路,所有可能的组合都做一遍。

(3)动态规划(DP):解题思路

依据上面算法特征分析的基础上,使用一个数组动态存储n的计算结果。

初始化数组,预先存入n-1和n-2的结果

def climbStairs(n):
    if n <= 1:
        return n
    dp = [i for i in range(n+1)]
    for i in range(3,n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[-1]

上面代码中的dp就是我们提到的数组,其中dp[i] = dp[i-1] + dp[i-2]

循环执行完成后,数组中最后一次计算的结果就是爬n阶楼梯的方法数。

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

对于空间复杂度,还可以进一步优化。由于我们只考虑n以及n-1、n-2的值。所以,中间的过程值可以丢弃。定义一个固定长度的数组,每次计算结果动态覆盖,如下:

def climbStairs(n):
    if n <= 1:
        return n
    dp = [0,1,2]
    for i in range(3,n+1):
        sum = dp[1] + dp[2]
        dp[1] = dp[2]
        dp[2] = sum
    return dp[2]
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

(4)动态规划理论

        学习动态规划算法,是从多种题解的思路中学习和发现。众多技术高手都给出了思路和技巧,但从实际出发,建议还是先埋头做题,积累了练习和分析思考后,再进行看高手的总结和归纳才会有“英雄所见略同”的共识。

在这之前,针对每道题目的分析,希望能思考如下的几个问题:

  • 题目计算的目标是什么

    走台阶问题的目标是求走法组合总数

  • 计算分解的子问题是什么

    (n-1)阶走法 、(n-2)阶走法就是n阶走法的子问题 ****

  • 转移方程是否是子问题的组合

    转移方程上面已经写出来了 f(n) = f(n-1)+f(n-2) 。

  • 能否优化

    使用动态数组或字典来存储中间结果,可以有效的减少重复计算的复杂度。

    当然,涉及到使用数组等容器来实现计算和优化时,还会接触到背包问题。

上一篇:区块链行业低迷的原因及未来发展展望


下一篇:【C++】多态