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))
    }

引用声明

该题目引用自
牛客网