一.解法
https://leetcode-cn.com/problems/climbing-stairs/
要点：dp动态规划
标准的动态规划，实际上是个斐波那契数列
Python，C++，Java都用了动态规划
转移方程是dp(n)=dp(n-1)+dp(n-2)
二.Python实现
class Solution:
def climbStairs(self, n: int) -> int:
dp=[]
dp.append(1)
dp.append(1)
for i in range(2,n+1):
dp.append(dp[i-2]+dp[i-1])
return dp[n]
三.C++实现
class Solution {
public:
int climbStairs(int n) {
vector<int> dp;
dp.push_back(1);
dp.push_back(1);
for(int i=2;i<=n;i++){
dp.push_back(dp[i-2]+dp[i-1]);
}
return dp[n];
}
};
四.java实现
class Solution {
public int climbStairs(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
