【LeetCode】 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?

Note: Given n will be a positive integer.

解题思路

动态规划。 由于每次只能够走一步或者两步，那么，能够到达当前阶级，有两种可能：

在下一级阶级中一次走一步达到在下两级阶级中一次走两步到达

于是，有如下的状态转移方程：

dp[k] = dp[k - 1] + dp[k - 2]

AC代码

class Solution { public: int climbStairs(int n) { int *dp = new int[n]; dp[0] = 1; dp[1] = 2; for (int k = 2; k < n; ++k) { dp[k] = dp[k - 1] + dp[k - 2]; } int ans = dp[n - 1]; if (dp != NULL) { delete dp; dp = NULL; } return ans; } };