https://leetcode.com/problems/climbing-stairs/
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer. 思路: 总结发现每次走的步数都是fibonacci数
关键词:dynamic programming, fibonacci
Time & Space complexity: O(n) O(1)
public class Solution { public int climbStairs(int n) { //n steps has fibonacci(n) ways to get if(n<2){ return n;} int i = 1; int a = 1; int b =1; int res = 0; while(i<n){ res = a+ b; a = b; b = res; i++; } return res; } }
No comments:
Post a Comment