Menu

恰恰舞中女士连续后退走步



澳门新葡亰6609 1


You are climbing a stair case. It takes n steps to reach to the
top.
Each time you can either climb 1 or 2 steps. In how many distinct ways
can you climb to the top?

Note : Given n will be a positive integer.

恰恰舞中的连续恰恰恰,是很有特色的步伐,在非街头跳法中,女士后退的恰恰恰有很多种变化,这里详细的解析一下。 第一种是连续三个后退的恰恰,这是最简单而又没有变化的方式。有一些单调,但是好跳一些。 第二种是左脚向后的恰恰,然后右脚向后的恰恰,然后迅速转身180度,女士变为向前的恰恰,带着男士向前。这里,转身要求很快,容易跟不上节拍,重心不稳。 第三种则是变形后,先是左脚向后的恰恰,然后右脚向后恰,时左脚到右脚前,one时右脚并不向后迈出,而是静止停顿,此时两人的距离就一下子拉近了很多。接下来迅速转身180度,女士做左脚在前,向前的恰恰,向前的第一步要大,这样两人之间的距离再次拉大,在时右脚并到左脚的后面做check,one时以左脚为轴,女士转回180度,左脚脚尖旁点地,面向男士,就又回到了两人开式状态,此时可以停止一拍,延伸动作,女士上半身前倾。这样做会使得动作看起来有急有缓,两个人之间的情感交流也比较多,看起来专业了很多。注意旋转时动力腿的脚尖拖地画圆,呈现突出的圆规腿的感觉,带上甩头和呼吸。

思路:

  • 如果只有1 级台阶,只有一种跳法;
    如果有2 级台阶,那就有两种跳的方法了:一种是分两次跳,每次跳1
    级;另外一种就是一次跳2 级。
    如果有3级台阶,那就有4种跳的方法:一种是分3次跳,每次跳1级;另一种是一次跳1级,一次跳2级(调换过来也是一种);另一种是一次就跳3级;

  • 一般情况:把n 级台阶时的跳法看成是n 的函数,记为f(n)。
    当n>3 时,第一次跳的时候就有3种不同的选择:

    • 一种是第一次只跳1 级,此时跳法数目等于后面剩下的n-1
      级台阶的跳法数目,即为f(n-1);
    • 另外一种选择是第一次跳2 级,此时跳法数目等于后面剩下的n-2
      级台阶的跳法数目,即为f(n-2);
    • 另外一种选择是第一次跳3 级,此时跳法数目等于后面剩下的n-3
      级台阶的跳法数目,即为f(n-3)。
  • 澳门新葡亰6609 ,因此n 级台阶时的不同跳法的总数f(n) = f(n-1) + f(n-2) + f(n-3)。
    时间复杂度:O(n)

public class Test {
    public static void main(String[] args) {
        System.out.println(jump(4));
    }

    private static int jump(int step) {
        // TODO Auto-generated method stub
        if(step <= 0) {
            return 0;
        }
        if(step == 1 || step == 2) {
            return step;
        }
        if(step == 3) {
            return step + 1;    //包括自身
        }
        return (jump(step - 1) + jump(step - 2) + jump(step - 3));
    }
}

输出结果是:7

本题对应于《剑指offer》P75的跳台阶问题:

恰恰舞小贴士第三种跳法也是近年来流行的跳法,跳起来省力而且视觉效果好了很多,就能出现男女情感之间交流、追逐、回应的一个感觉。

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

首先我们考虑最简单的情况。如果只有1级台阶,那显然只有一种跳法。如果有2级台阶,那就有两种跳法了:一种是分两次跳,每次跳1级;另外一种就是一次跳2级。

接着我们再来讨论一般的情况。把n级台阶时的跳法看成是n的函数f(n)。当n>2时,第一次跳的时候有两种不同的选择

  • 第一次只跳1级,此时跳上n级台阶的跳法数目等于后面剩下的n-1级台阶的跳法数目,即f(n-1)
  • 第一次跳2级,此时跳上n级台阶的跳法数目等于后面剩下的n-2级台阶的跳法数目,即f(n-2)

因此n级台阶的不同跳法的总数 f(n) = f(n-1) + f(n-2)

上面的分析过程,我们用到了动态规划的方法,找到了状态转移方程,不难看出这实际上就是一个类斐波那契数列,只是初始条件与传统的斐波那契数列略有不同,这里f(2)=2。

关于斐波那契数列,我在之前的文章中已经详细分析了这类问题的三种计算机解法:自上而下的递归实现太耗时,转化为特征矩阵的乘方又太复杂,所以一般使用自底向上的迭代算法。

应用自底向上的迭代算法求解本题的源码如下,其时间复杂度为O(n)

public class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int fibCurrent = 0, fibOneBack = 2, fibTwoBack = 1;
        for (int i = 3; i <= n; i++) {
            fibCurrent = fibOneBack + fibTwoBack;
            fibTwoBack = fibOneBack;
            fibOneBack = fibCurrent;
        }
        return fibCurrent;
    }
}

系统准备一个函数,是常数项时间复杂度比较大的事情,而且系统递归栈的大小也是有限的,所以工程上的代码,很少使用递归。对于一种算法的递归版本,往往可以通过自己维护一个栈或者迭代的方式,将其改写成非递归版本进行优化。


《剑指offer》上还对本题进行了如下扩展

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

首先我们仍然考虑最简单的情况。如果只有1级台阶,那显然只有一种跳法。如果有2级台阶,那就有两种跳法了:一种是分两次跳,每次跳1级;另外一种就是一次跳2级。

接着我们再来讨论一般的情况。把n级台阶时的跳法看成是n的函数f(n)。当n>2时,第一次跳的时候有n种不同的选择

  • 第一次只跳1级,此时跳上n级台阶的跳法数目等于后面剩下的n-1级台阶的跳法数目,即f(n-1);
  • 第一次跳2级,此时跳上n级台阶的跳法数目等于后面剩下的n-2级台阶的跳法数目,即f(n-2);
  • 第一次跳3级,此时跳上n级台阶的跳法数目等于后面剩下的n-3级台阶的跳法数目,即f(n-3);
  • ……;
  • 第一次跳n-1级,此时跳上n级台阶的跳法数目等于后面仅剩的1级台阶的跳法数目,即f(1);
  • 从初始位置直接跳n级,这也对应了一种跳法

综上所述,n级台阶的不同跳法的总数 f(n) = f(n-1) + f(n-2) + f(n-3) + …

  • f(1) + 1
    把n-1带入上面的递推式得 f(n-1) = f(n-2) + f(n-3) + … + f(1) + 1
    所以最终的递推式为 f(n) = 2 * f(n-1)
    应用自底向上的迭代算法求解本题的源码如下:

    public class Solution {

      public int climbStairs(int n) {
          int result = 1;
          if (n == 1) {
              return result;
          }
          for (int i = 2; i <= n; i++) {
              result *= 2;
          }
          return result;
      }
    

    }

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章

网站地图xml地图