题解 | #跳台阶扩展问题#

跳台阶扩展问题

https://www.nowcoder.com/practice/953b74ca5c4d44bb91f39ac4ddea0fee

注意题目要求时间复杂度O(1),那么肯定有一个公式可以直接得出答案。

第 1 级台阶,0 级基础上跳 1 级
第 2 级台阶,第 1 级基础上跳,0 级基础上跳 2 级
第 3 级台阶,第 1 级基础上跳,第 2 级基础上跳,0 级基础上跳 3 级
第 4 级台阶,第 1 级基础上跳,第 2 级基础上跳,第 3 级基础上跳,0 级基础上跳 4 级
......
第 n 级台阶,第 1 级基础上跳,第 2 级基础上跳,......,第 n-1 级基础上跳,0 级基础上跳 n 级

可得 f(n) = f(n-1)+f(n-2)+...+f(1)+1
由于 f(n-1) = f(n-2)+f(n-3)+...+f(1)+1
因此 f(n) = f(n-1)+f(n-1) = 2f(n-1)
所以 {fn} 是等比数列,公比 q 等于2。
根据等比数列公式 fn = f(1)*q^(n-1)。
所以就有 fn = 2^(n-1)

完整 Java 版代码
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(new Solution().solution(n));
    }
}

class Solution {
    public int solution(int n) {
        return (int)Math.pow(2, n-1);
    }
}


全部评论

相关推荐

07-11 22:27
中南大学 Java
程序员牛肉:学历的话没问题。但是没问题的也就只有学历了。 其实你的整体架构是正确的,博客接着干。但是项目有点过于简单了。从后端的角度上讲,你这也就是刚入门的水平,所以肯定约面试够呛。 如果你要应聘后端岗位,那你第一个项目竟然是仿写操作系统。这个你要面试官咋问你。你一定要记住一点,你简历上写的所有的东西,都是为了证明你有能力胜任当前的岗位,而不是为了证明你自己会什么。 如果你只是浅浅的做几个项目,描述也都是烂大街。技术点也都是各种混水类的配置类需求,那你就不要幻想自己能走多远。一定要保持思考,保持学习。
点赞 评论 收藏
分享
评论
11
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务