[剑指-09](php&python):变态跳台阶

说明：记录刷剑指offer，使用php与python两种语言，对解题思路以及涉及到的基本语法以及知识点做学习记录。其中对于每道题目进行粗略的分类。

题目来源

• 分类：递归
• 变态跳台阶

题目描述

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

解题思路

对于本题，每次只有1阶，2阶，3阶.....n种跳法

• 假设第一次跳的是一阶，则剩余的(n-1)阶，有f(n-1)种跳法
• 假设第一次跳的是二阶，则剩余的(n-2)阶，有f(n-2)种跳法
• 假设第一次跳的是三阶，则剩余的(n-3)阶，有f(n-3)种跳法
  .....
• 假设第一次跳的是(n - 1)阶，则剩余的1阶，有f(1)种跳法。
• 所以n阶台阶有f(n) = f(1) + f(2) + f(3) + f(4) +...+ f(n-2) + f(n - 1)种跳法，其中f(n - 1) = f(1) + f(2) + f(3) + f(4) + ... + f(n - 2)；则f(n) = 2f(n - 1)。

编程实现

PHP

<?php
    运行时间：26ms

    占用内存：2776k
    function jumpFloorII($number)
    {
        // write code here
        if ($number <= 0){
            return -1;
        } elseif ($number == 1) {
            return 1;
        } else {
            return 2 * jumpFloorII($number - 1);
        }
    }
// 根据等比数列性质：an = a1 * q^(n-1) 此题 an = 2^(n - 1)
    function jumpFloorI($number)
    {
        if($number == 0){
            return 0;
        } 
        $total = 1;
        for($i = 1; $i < $number; $i++){
            $total *= 2;
        }
        return $total;
        
    }

?>

Python

# -*- coding:utf-8 -*-
class Solution:
    '''
    递归的方式： 27ms 5728k
    '''
    def jumpFloorI(self, number):
        if number <= 0:
            return -1
        elif number == 1:
            return 1
        else:
            return 2 * self.jumpFloorI(number - 1)

    '''
    第二种做法：f(n)=2f(n-1)是等比数列，首项为1，比例 为2，f(n)=2^(n-1)  23ms 5748k
    '''
    def jumpFloorII(self, number):
        return 2**(number - 1)