爬楼梯,那么一次爬一步,要么一次爬两步。问你有几种爬法?
搜索?
会超时
后来改成迭代:
a[n] = a[n-1] + a[n-2]
一次AC
class Solution { public: int climbStairs(int n) { // Note: The Solution object is instantiated only once and is reused by each test case. int a1 = 1; int a2 = 2; if(n == 1) { return a1; } if(n == 2) { return a2; } int index = 3; int before = a2; int now = a1 + a2; while(true) { if(index == n) { return now; } int tmp = before; before = now; now = tmp + before; index++; } } };