题目:
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/climbing-stairs
思路:
使用动态规划的基本思想,到第n个台阶的方法等于到n-1和n-2台阶时的方法之和。
Python解法:
1 class Solution: 2 def climbStairs(self, n: int) -> int: 3 if n==0 or n==1 or n==2: return n 4 else: 5 way = {} 6 way[1] = 1 7 way[2] = 2 8 for i in range(3, n+1): 9 way[i] = way[i-1] + way[i-2] 10 return way[i]
C++解法:
1 class Solution { 2 public: 3 int climbStairs(int n) { 4 if(n == 1 || n == 2) return n; 5 vector<int> stairs; 6 stairs.push_back(0); // 此处不能使用stairs[0]=0的写法,必须用push_back,因为未指定元素个数,vector为空, size为0,表明容器中没有元素,而且 capacity 也返回 0,意味着还没有分配内存空间。 7 stairs.push_back(1); 8 stairs.push_back(2); 9 for(int i = 3; i <= n; i++) { 10 int temp = 0; 11 temp = stairs[i-1] + stairs[i-2]; 12 stairs.push_back(temp); 13 } 14 return stairs[n]; 15 } 16 };