动态规划(一):爬楼梯

题目

一个

阶的楼梯,每次能走 1~2 阶,问走到

阶一共多少种走法

分析

因为每次能走 1~2 阶,所以第

阶的前一个状态可以是第

阶,或第

,且只有这两种情况。

解答

表示到达第

阶的所有走法个数,当

时,则有:

时,处于原地,因为步长为 1 ~ 2 阶,不能有前进之后再后退的情况,所以只能有当前一种方式,所以

时,只能选择步长为 1 一种方式,所以

根据此推到公式可以有如下解法。

递归形式

def climbingStairs(n):
    if n == 0 or n == 1:
        return 1
    return climbingStairs(n-1) + climbingStairs(n-2)

递归形式的时间复杂度为

,空间复杂度为

时间复杂度参考斐波那契数列的时间复杂度 Time complexity of recursive Fibonacci program, 因为递归栈数最深为

层,所以空间复杂度为

迭代形式

递归形式算法的时间复杂度呈指数级增长,所以这种算法较为不现实。观察递推关系式:

可以发现,每个阶梯数的函数值,只与其前两项的函数值有关,所以不妨由低到高进行推导。

def climbingStairs(n):
    a, b, i = 1, 1, 2
    while i <= n:
        a, b, i = b, a + b, i + 1
    return b

表示

,迭代更新

的值,即可得出最后的结果。时间复杂度为

,空间复杂度为

矩阵形式

根据递推关系式,对二阶差分方程构造矩阵:

根据

的递推关系式, 可得:

import numpy as np
import math
def climbingStairs_matrix(n):
    unit = np.array([[1, 1], [1, 0]])  
    target, result = n - 1, np.identity(2, int)  # target means the total index
    while target > 1:
        index, tmp = 1, unit
        times = int(math.log2(target))  # the iterations times
        while index <= times:
            tmp, index = np.dot(tmp, tmp), index + 1
        result = np.dot(tmp, result)
        target = target - 2 ** times
    result = np.dot(unit, result) if target == 1 else result
    result = np.dot(result, np.array([[1], [1]]))
    return result[0][0]
  • 最好情况下

以求

值为例,若

,则有如下分析:

若已知

,因为

,则只需要一次计算即可;

若已知

,因为

,则得出

值需要两次计算,首先计算出

,然后计算出

; ... ... ... 若已知

,则计算出

需要

次计算,即计算

值的时间复杂度为

即最好情况下矩阵运算的时间复杂度为

,空间复杂度为

  • 最坏情况下

以求

值为例,若

,则有:

由最好情况分析结论知,

的计算次数为

。若已知

,则得出

的值需要

次计算。

递推有:

由最好情况分析结论知,

的计算次数为

。若已知

,则得出

的值需要

次计算。 ... ... ...

则得出

的值需要

次计算。

即最坏情况下矩阵运算的时间复杂度为

,空间复杂度为

若使用逆矩阵,则逆矩阵的个数

存在同样问题,所以此处不涉及逆矩阵运算。

保留中间状态的矩阵形式

观察以上矩阵形式的代码可知,非最优场景下的计算过程存在重复运算,虽然通过对数形式降低了重复的次数,但依然存在计算能力的浪费。针对该情况,申请空间保留中间计算状态。

def climbingStairs_matrix(n):
    unit = np.array([[1, 1], [1, 0]])  # M represents the unit matrix
    arr, target, result = [unit], n - 1, np.identity(2, int)  # target means the total index
    while target > 1:
        index, tmp = 1, unit
        times = int(math.log2(target))  # the iterations times
        if times >= len(arr):
            while index <= times:
                tmp, index = np.dot(tmp, tmp), index + 1
                arr.append(tmp)
        else:
            tmp = arr[times]
        result = np.dot(tmp, result)
        target = target - 2 ** times
    result = np.dot(unit, result) if target == 1 else result
    result = np.dot(result, np.array([[1], [1]]))
    return result[0][0]

代码中增加

数组保存中间的计算状态,其中

表示

的值。该形式的矩阵运算时间复杂度为

,空间复杂度为

拓展形式

当步长调整为 1~

阶时,问走到

阶一共多少种走法

递归形式
def climbingStairs(n, m):
    if n == 0:
        return 1
    stepSize, result = n if m >= n else m, 0
    for i in range(1, stepSize + 1):
        result += climbingStairs4(n - i, m)
    return result

递归关系式由

更新为

,增加步长

的大小关系判断。

迭代形式
def climbingStairs(n, m):
    if n <= 1 or m == 1:
        return 1
    stepSize = n if m >= n else m
    arr = [0] * stepSize
    arr[0], arr[1], index, tmp = 1, 1, 2, 1
    while index <= n:
        if index > stepSize:
            tmp, arr[index % stepSize] = arr[index % stepSize], arr[(index - 1) % stepSize] * 2 - tmp
        else:
            arr[index % stepSize] = arr[(index - 1) % stepSize] * 2
        index += 1
    return arr[(index - 1) % stepSize]

时间复杂度与步长为 1 ~ 2 时相同,为

。因为需要申请空间存储中间状态数据,所以空间复杂度为

,其中

表示最大步长。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏潇涧技术专栏

Python Algorithms - C6 Divide and Combine and Conquer

Python算法设计篇(6) Chapter 6: Divide and Combine and Conquer

13120
来自专栏java一日一条

成为优秀Swift开发者的10条建议

在这里给大家分享一些帮助大家成为更优秀的Swift开发者的建议,让你的代码,写的更少,性能更优 。

12420
来自专栏阿凯的Excel

文本数字拆分技巧

Excel处理人员呢,最喜欢的就是规范化的表,那什么样子的表是规范的呢?给大家个图片感受一下! ? 今天的要和大家分享的就是和规范化图表格格不入的,需要由不规...

35060
来自专栏计算机视觉与深度学习基础

HDU2066

神坑的题目 思路就是枚举起点,迪杰斯特拉求最短路径,再枚举终点(如果起点终点一起枚举可能会超时,也能勉强扯上动态规划的思想吧),求最短路径。 如果剪枝可以加一个...

24370
来自专栏C/C++基础

统计无符号整数二进制中1的个数(Hamming weight)

之所以来记录这个问题的解法,是因为在在线编程中经常遇到,比如编程之美和京东的校招笔试以及很多其他公司都累此不疲的出这个考题。看似简单的问题,背后却隐藏着很多精妙...

18220
来自专栏阿凯的Excel

让你眼花缭乱的匹配函数反查技巧

小编已经连续写了三期关于匹配函数的用法,匹配函数的扛把子(老大)肯定是Vlookup函数莫属,但是Vlookup函数有一个问题,就是要查找的内容,必须在查找内容...

30560
来自专栏小詹同学

Leetcode打卡 | No.012 整数转罗马数字

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

12510
来自专栏desperate633

[编程题] 猜数游戏分析代码

首先我们分析,dp[i]表示前i个数的合法个数 当第i个数是素数的时候,前面除了1都没有能除尽的,所以这个位置可以随便选Y或N,所以dp[i] = dp[i-...

12530
来自专栏量化投资与机器学习

【精心解读】用pandas处理大数据——节省90%内存消耗的小贴士

本文我们讨论 pandas 的内存使用,展示怎样简单地为数据列选择合适的数据类型,就能够减少 dataframe 近 90% 的内存占用。

1.8K50
来自专栏阿凯的Excel

筛选功能(Pandas读书笔记9)

今天和大家分享如果使用Pandas实现单、多条件筛选、模糊筛选。 还是老套路,我们需要先读取一组数据作为测试文件。 测试文件使用读书笔记7的材料,传送门如下: ...

1.4K60

扫码关注云+社区

领取腾讯云代金券