假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
动态规划题
Python
class Solution: def climbStairs(self, n: int) -> int: if n<=2: return n dp = [0]*(n+1) dp[0]=1 dp[1]=1 dp[2]=2 sum = 0 for i in range(3,n+1): sum = dp[2] + dp[1] dp[1] = dp[2] dp[2] = sum print(sum) return sum
C++
class Solution { public: int climbStairs(int n) { vector<int> dp(n+1); //初始化数组 if (n<=2){ return n; } dp[0] = 0; dp[1] = 1; dp[2] = 2; for(int i=3;i<n+1;i++) { dp[i] = dp[i-2] + dp[i-1]; } return dp[n]; } };
空间复杂度:O(n)
时间复杂度:O(n)
优化:
class Solution { public: int climbStairs(int n) { vector<int> dp(3); //初始化数组 if (n<=2){ return n; } dp[0] = 0; dp[1] = 1; dp[2] = 2; int sum = 0; for(int i=3;i<n+1;i++) { sum = dp[1] + dp[2]; dp[1] = dp[2]; dp[2] = sum; } return sum; } };
空间复杂度:O(1)
时间复杂度:O(n)