leetcode 70. Climbing Stairs (easy)

1. dp
   第i个阶梯一定是从第i-1个阶梯上来或者第i-2个阶梯上来的

class Solution
{public:int climbStairs(int n){int dp[n + 1];memset(dp, 0, sizeof(dp));dp[0] = 1;dp[1] = 1;for (int i = 2; i <= n; i++){dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
};

2. 迭代

class Solution
{public:int climbStairs(int n){int cur = 1;int pre = 0;for (int i = 0; i < n; i++){int temp = cur;cur += pre;pre = temp;}return cur;}
};