美文网首页
剑指offer-贪心跳台阶

剑指offer-贪心跳台阶

作者: 纳萨利克 | 来源:发表于2019-09-28 14:50 被阅读0次

    一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

    思路
    跳n级台阶=
    第一次跳n(1)+
    第一次跳n-1,剩下跳1级(1)+
    第一次跳n-2,剩下跳2级(2)+
    第一次跳n-3,剩下跳3级(4)+
    ...
    第一次跳3,剩下跳n-3级+
    第一次跳2,剩下跳n-2级+
    第一次跳1,剩下跳n-1级

    f(n) = f(n-1) + f(n-2) + ... + f(1) + f(0)
    f(n-1) = f(n-2) + ... + f(1) + f(0)
    => f(n) = 2f(n-1)

    Java

    public class Solution {
        public int JumpFloorII(int target) {
            if (target <= 2) {
              return target;
            }
            return JumpFloorII(target-1)*2;
        }
    }
    

    不使用递归

    public class Solution {
      public int JumpFloorII(int target) {
        if (target <= 2) {
          return target;
        }
        int sum = 2;
        for (int i = 3; i <= target; i++) {
          sum = 2*sum;
          
        }
        return sum;
      }
    }
    

    相关文章

      网友评论

          本文标题:剑指offer-贪心跳台阶

          本文链接:https://www.haomeiwen.com/subject/qoxtpctx.html