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?
解析:
本题是个动态规划问题,最优解可有子问题的的最优解组成,具有重复的子问题,
leetcode | Climbing Stairs
。由题目可知要求到达第n阶台阶的所有方法f(n),又每次能登1~2个台阶,
- 从 n-1 阶登 1 步 到达 n 阶
- 从 n-2 阶登 2 步 到达 n 阶
因此
难点在于想到递归式,对于递归问题注意从后往前看,电脑资料
《leetcode | Climbing Stairs》(http://meiwen.anslib.com)。
<code class="hljs vala">class Solution {public: // f(n) = f(n-1)+f(n-2) int climbStairs(int n) { int prev = 0; int cur = 1; for(int i = 1; i <= n; i++) { int temp = cur; cur += prev; prev = temp; } return cur; }};</code>