leetCode 70. Climbing Stairs | 动态规划

70. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

思考：

top

steps

1

2

3

4

5

8

6

13

...

从上面的分析可以看出，f(top) = f(top - 1) + f(top - 2)

使用动态规划，确定当前登到第i级台阶可能的步数是几。然后在查看下一级i+1台阶的可能步数。

代码实现如下：

7

9

10

11

12

14

15

16

17

18

19

20

21

<code>class</code> <code>Solution {</code>

<code>public</code><code>:</code>

<code>    </code><code>int</code> <code>climbStairs(</code><code>int</code> <code>n) </code>

<code>    </code><code>{</code>

<code>        </code><code>if</code> <code>(n &lt;= 0)</code>

<code>            </code><code>return</code> <code>0;</code>

<code>        </code><code>if</code> <code>(n &lt;= 2)</code>

<code>            </code><code>return</code> <code>n;</code>

<code>    </code> 

<code>        </code><code>int</code> <code>a[2] = {1,2};</code>

<code>        </code><code>int</code> <code>tmp = 0;</code>

<code>        </code><code>for</code> <code>(</code><code>int</code> <code>i = 0; i &lt; n - 2; ++i)</code>

<code>        </code><code>{</code>

<code>            </code><code>tmp = a[0] + a[1];</code>

<code>            </code><code>a[0] = a[1];</code>

<code>            </code><code>a[1] = tmp;</code>

<code>        </code><code>}</code>

<code>        </code><code>return</code> <code>tmp;</code>

<code>    </code><code>}</code>

<code>};</code>

总结：

先确定当前的结果，然后转移。确定下一步的结果。依次转移，直到结果。

本文转自313119992 51CTO博客，原文链接:http://blog.51cto.com/qiaopeng688/1844815