Swift-n阶台阶问题
2017-05-12 本文已影响3人
FlyElephant
题目:楼梯有n阶台阶,每次可以上1阶、2阶或3阶,计算上楼梯的方式有多少种.
解法一
<pre><code>` func countStepWays(n:Int) -> Int {
if n < 0 {
return 0
} else if n == 0 {
return 1
} else {
return countStepWays(n:n - 1) + countStepWays(n: n - 2) + countStepWays(n: n - 3)
}
}`</code></pre>
解法二
<pre><code>` func countStepWays2(n:Int,map:inout [Int]) -> Int {
if n < 0 {
return 0
} else if n == 0 {
return 1
} else if map[n] > -1 {
return map[n]
} else {
map[n] = countStepWays2(n: n - 1, map: &map) + countStepWays2(n: n - 2, map: &map) + countStepWays2(n: n - 3, map: &map)
return map[n]
}
}`</code></pre>
测试代码:
<pre><code>var steps:Int = recursion.countStepWays(n: 10) var map:[Int] = [Int].init(repeating: -1, count: 11) var steps2:Int = recursion.countStepWays2(n: 10, map: &map) print("FlyElephant--跳10级台阶的跳法---\(steps)-----\(steps2)")
</code></pre>