70、爬楼梯

题目

解答

简单dp，边界条件n=1为1，n=2为2，递推即可

class Solution {
public:int climbStairs(int n) {if (n == 1)return 1;if (n == 2)return 2;// 递推：dp[n]=dp[n-1]+dp[n-2]int last = 2;int llast = 1;int ans = 0;for (int i = 3; i <= n; i++) {ans = last + llast;llast = last;last = ans;}return ans;}
};

时间复杂度O(n)

空间复杂度O(1)