8.2 变态跳台阶

题目描述

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

解题思路

对于本题,有 一次 1阶或者2阶的跳法,也有一次n阶的跳法。

f(1) = 1

f(2) = f(2-1) + f(2-2)         //f(2-2) 表示2阶一次跳2阶的次数。

f(3) = f(3-1) + f(3-2) + f(3-3) 

...
f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n) 
  1. n = 1时,只有1种跳法,f(1) = 1
  2. n = 2时,会有一次1阶或者2阶两种跳的方式,,这回归到了问题(1) ,f(2) = f(2-1) + f(2-2)
  3. n = 3时,会有1阶、2阶、3阶,三种跳的方式;那么就是第一次跳出1阶后面剩下:f(3-1);第一次跳出2阶,剩下f(3-2);第一次3阶,那么剩下f(3-3)
    则: f(3) = f(3-1) + f(3-2) + f(3-3)
  4. n = n时,会有,1阶、2阶…n阶;总共n中跳的方式,则:f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... f(n-2)+ f(n-1)
  5. 上面4的表达式可以看到f(n) = f(0)+f(1)+...+f(n-2)+f(n-1), f(n-1) = f(0)+f(1)+...+f(n-2);则f(n) = f(n-1)+f(n-1)简化后可以写成:f(n) = 2 * f(n-1)
f(n) = 2*f(n-1)=2^2 * f(n-2)= ... = 2^{n-1} * f(1)  = 2^{n-1}

代码实现

java 代码

/**
 * 递归变态跳台阶,可以跳1阶,2阶...n阶
 * 时间复杂度 O(n)
 * @param n 总阶数
 * @return
 */
public int jumpFloorII(int n) {
    if (n == 1) {
        return 1;
    } else {
        return 2 * jumpFloorII(n - 1);
    }
}

/**
 * 数学公式发变态跳台阶,可以跳1阶,2阶...n阶
 * ∵ f(n) = f(0)+f(1)+...+f(n-2)+f(n-1)
 * f(n-1) = f(0)+f(1)+...+f(n-2)
 * ∴ f(n) = f(n-1)+f(n-1)
 * f(n) = 2 * f(n-1)=2^2 * f(n-2)= ... = 2^{n-1} * f(1)  = 2^{n-1}
 * 时间复杂度 O(1)
 * @param n 总阶数
 * @return
 */
public int jumpFloorIIMath(int n) {
    return (int) Math.pow(2, n - 1);
}

/**
 * 迭代发变态跳台阶,可以跳1阶,2阶...n阶
 * 时间复杂度 O(n)
 * @param n 总阶数
 * @return
 */
public int jumpFloorIIFor(int n) {
    if (n == 1) {
        return 1;
    } else {
        int c = 1;
        for (int i = 2; i <= n; i++) {
            c *= 2;
        }
        return c;
    }
}

public static void main(String[] args){
     System.out.println(jumpFloorII(9));
    System.out.println(jumpFloorIIMath(9));
    System.out.println(jumpFloorIIFor(9));
}

Kotlin 代码

 /**
  * 递归变态跳台阶,可以跳1阶,2阶...n阶
  * 时间复杂度 O(n)
  * @param n 总阶数
  * @return
  */
 private fun jumpFloorII(n: Int): Int {
     return if (n == 1) {
         1
     } else {
         2 * jumpFloorII(n - 1)
     }
 }

 /**
  * 数学公式发变态跳台阶,可以跳1阶,2阶...n阶
  * ∵ f(n) = f(0)+f(1)+...+f(n-2)+f(n-1)
  * f(n-1) = f(0)+f(1)+...+f(n-2)
  * ∴ f(n) = f(n-1)+f(n-1)
  * f(n) = 2 * f(n-1)=2^2 * f(n-2)= ... = 2^{n-1} * f(1)  = 2^{n-1}
  * 时间复杂度 O(1)
  * @param n 总阶数
  * @return
  */
private fun jumpFloorIIMath(n: Int): Int {
     return 2.0.pow(n - 1.toDouble()).toInt()
 }

 /**
  * 迭代发变态跳台阶,可以跳1阶,2阶...n阶
  * 时间复杂度 O(n)
  * @param n 总阶数
  * @return
  */
 private fun jumpFloorIIFor(n: Int): Int {
     return if (n == 1) {
         1
     } else {
         var c = 1
         for (i in 2..n) {
             c *= 2
         }
         c
     }
 }

 /**
  * 入口函数
  */
 fun main(args: Array<String>) {
     println(jumpFloorII(9))
     println(jumpFloorIIMath(9))
     println(jumpFloorIIFor(9))
 }

引用声明

该题目引用自
牛客网