初级算法-动态规划-爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

摘一个示例做个说明.
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

条件分析:

1. 总共n阶,每次只能走一阶或者两阶

解决思路1:

1. 根据分析1,走台阶可以从第一步开始,当n为1时,上一步.n为2的时候上两步或者一步.做个列举
   n 为 1, 结果为 1 (1)
   n 为 2, 结果为 2 (1,1)(2)
   n 为 3, 结果为 3 (1,1,1)(1,2)(2,1)
   n 为 4, 结果为 5 (1,1,1,1)(1,1,2)(1,2,1)(2,1,1)(2,2)
   n 为 5, 结果为 8 (1,1,1,1,1)(1,1,1,2)(1,1,2,1)(1,2,1,1)(1,2,2)(2,1,1,1)(2,1,2)(2,2,1)
2. 发现每一个都是前两次相加的结果.所以整理为数学形式就是f(n) = f(n - 1) + f(n - 2).特殊情况除外.至此,算法就转换为数学题了.斐波那契数列可以了解一下.

采用斐波那契数列方式计算

func climbStairs(_ n: Int) -> Int {
    if n == 1 || n == 2 {
        return n
    }
    var fx: Int = 0
    var fy: Int = 1
    var total: Int = fx + fy
    for _ in 2 ..< n + 1 {
        fx = fy
        fy = total
        total = fx + fy
    }
    return total
}

爬楼梯提交结果.jpg

本文采用递归也可以,不过,当n稍微大一点就超时了.

func climbStairs(_ n: Int) -> Int {
    if n == 1 || n == 2 {
        return n
    }
    return climbStairs(n - 1) + climbStairs(n - 2)
}

测试用例:

// 最小
let n = 1
// 最小
let n = 2
// 正常
let n = 4
let n = 14
let n = 24
let n = 34
let n = 114

考察要点:

• 记忆化搜索
• 数学
• 动态规划