leetcode-70.爬楼梯

/* * @lc app=leetcode.cn id=70 lang=csharp * * [70] 爬楼梯-斐波那契数列 f(n) = f(n-2) + f(n-1) 数学归纳法-递推 1：1-->f(1) = 1 2：2-->从1级走过来；从0直接走过来f(2) = 2 3：3-->只能从1和2走过来，所以3的解法共有1和2的解法和 f(3) = f(2) + f(1) 4:f(4) = f(2) + f(3) = f(2) + f(2) + f(1) 类推 f(n) = f(n-1) + f(n-2)-->只保留最近 重复 子阶段 时间复杂度 */ // @lc code=start public class Solution { public int ClimbStairs(int n) { //解法1：最近重复子问题 /*int f1 = 1; int f2 = 2; int f3 = f1 + f2; //int num = 0; if(n <= 2) return n; for(int i = 3; i < n; i++){ f1 = f2; f2 = f3; f3 = f1 + f2; } return f3;*/ //解法2：递归-会超时 if(n <= 2) return n; return ClimbStairs(n-1) + ClimbStairs(n-2); } } // @lc code=end