【剑指Offer】跳台阶

释放双眼,带上耳机,听听看~!

本文目录

题目描述

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

解法1

首先对这道题,我们可以通过找规律来解
一只青蛙可以跳上1级台阶,也可以跳上2两级台阶
当n = 1时,有1种跳法
当n = 2时,有2种跳法
当n = 3时,有3种跳法
当n = 4时,有5种跳法
当n = 5时,有8种跳法
...
等等,1,2,3,5,8...,多么熟悉的数列,斐波那契?
仔细想想当有n(n >= 2)级台阶时,求F(n)
青蛙第一步可以选择跳上1级台阶,则还剩n - 1级台阶需要跳,即F(n - 1)
青蛙第一步也可以选择跳上2级台阶,则还剩n - 2级台阶需要跳,即F(n - 2)
则总的跳法F(n) = F(n - 1) + F(n - 2),毫无疑问这就是斐波那契数列的定义了。
关于斐波那契的求解方法,读者可以参考【剑指Offer】斐波那契数列,包括了递归,动态规范,矩阵快速幂多种解法,这里就不再赘述了。
下面放上以求解斐波那契数列的方式解题的其中一种写法。

实现代码

public int jumpFloor(int number)
{
    int f1 = 0;
    int f2 = 1;
    while (number-- > 0)
    {
        f2 = f1 + f2;
        f1 = f2 - f1;
    }
    return f2;
}

排列组合

网上大多数的解法都是以求解斐波那契数列的思路来解题,但其实使用排列组合的思想也可以求解(真相是一开始没发现是斐波那契,才想到排列组合的-_-||)。
解题前先简单介绍下排列组合,摘自百度百科

  • 排列的定义:从n个不同元素中,任取m(m≤n,m与n均为自然数,下同)个元素按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列。从n个不同元素中取出m个元素的所有排列的个数,叫做从n个不同元素中取出m个元素的排列数,用符号A(n,m)表示。
    \\[A{^m_n} = n * (n - 1) * (n-2) * ... * (n-m+1) = \\frac{n * (n - 1) * (n - 2) * (n - m + 1) * (n - m) * ... * 2 * 1}{(n - m) * (n - m - 1) * (n - m - 2) * ... * 2 * 1} \\]
    \\[A{^m_n} = \\frac{n!}{(n - m)!}\\]
    其中n!表示n的阶乘,比如4! = 4 * 3 * 2 * 1
    对于\\[A{^m_n} = n * (n - 1) * (n-2) * ... * (n-m+1)\\]可以这样理解,当从n个元素中取第一个元素时,有n种取法。当再取第2个元素时,此时还剩n - 1个元素,有n - 1种取法。当再取第3个元素时,此时还剩n - 2个元素,有n - 2种取法。以此类推,当取到第m个元素时,此时还剩n - m + 1个元素,有n - m + 1种取法。则总取法为\\[n * (n - 1) * (n-2) * ... * (n-m+1)\\]
  • 组合的定义:从n个不同元素中,任取m(m≤n)个元素并成一组,叫做从n个不同元素中取出m个元素的一个组合。从n个不同元素中取出m个元素的所有组合的个数,叫做从n个不同元素中取出m个元素的组合数。用符号C(n,m) 表示。
    \\[C{^m_n} = \\frac{A{^m_n}}{m!} = \\frac{n!}{(n - m)!m!}\\]
    排列和组合的区别可以先简单理解为,从n个不同元素中,任取m个元素,有多少种取法,如果这m个元素的先后顺序不同,就认为是不同的取法的话,那么总取法数就是排列数A(n,m)。如果取出来的m个元素无论先后顺序如何,都认为是同一种取法,那么总取法数就是组合数C(n,m)。举个栗子,在{1,2,3,4,5}中任取三个数{2, 4, 5}或者{5,2,4},对于排列数来说,它们属于2种取法,而对于组合数来说它们只算1种取法。
    可以发现,排列和组合的区别在于取出来的这m个元素是否有顺序性。当有顺序性时,这m个元素有A(m,m)种排列顺序,所以排列数A(n,m)除以A(m,m),去除m个元素顺序性的影响,得到的就是组合数C(n,m),即
    \\[C{^m_n} =\\frac{A{^m_n}}{A{^m_m}} =\\frac{A{^m_n}}{m!} \\]

解法2

回到本题,青蛙可以跳上1级台阶,也可以跳上2级台阶,
对于n级台阶来说,它最多可以跳 n/2 次 2 级台阶,也就是说总的跳法数是跳0次2级台阶跳法数,1次2级台阶跳法数,2次2级台阶跳法数 ... n/2 次2级台阶跳法数的总和
现在问题就变成了求跳指定次数2级台阶的跳法数
假设有n级台阶,指定要跳m次2级台阶,还剩下n - 2m个1级台阶,则青蛙一共要跳n - 2m + m = n - m次才能跳完。即在n-m次跳跃中选择m次跳2级台阶,有多少种跳法数呢,C(n - m,m)种。(注意这里不是An - m,m),因为选出的m次2级台阶没有顺序性)
所以我们求出C(n - 1,1),C(n - 2,2),C(n - 3,3) .. C(n - n/2, n/2),然后将其相加,记得再加上1(选0个2级台阶,1种跳法),就是总的跳法数
实现代码时注意求组合数C(n,m)的算法,需要做一些优化,主要有两点
先化简公式
\\[C{^m_n} =\\frac{A{^m_n}}{m!} =\\frac{n * (n - 1) * (n-2) * ... * (n-m+1)}{m!} \\]
1,如果C(n,m)的结果用c#的int类型存储,则最大值为2^31^-1,如果按照公式依次计算分子和分母,可能分子或分母会超过2^31^-1,从而造成异常。所以优化为分子和分母的计算同步进行,当判断分子除以分母可以除整的时候,就先相除,避免累计数过大。后面的代码会有对应注释。
2,可以省略的计算就省略
比如求解C(5,4),其中的4 * 3 * 2,分子分母可以直接相约,本来分子分母的计算都需要连乘4次,现在只需要连乘1次
\\[C{^4_5} = \\frac{5 * 4 * 3 * 2}{4 * 3 * 2 * 1} \\]

实现代码

// 求解cnm
public int c(int n, int m)
{
    int count = m;
    int nf = 1, mf = 1;
    if (m >= n - m + 1)
    {
        // 对应优化2,只需要连乘n-m次
        count = n - m;
    }
    for (int i =0; i < count; i++)
    {
        nf *= (n - i);
        mf *= (i + 1);
        // 对应优化1,可以除整的时候就先除
        if (nf % mf == 0)
        {
            nf = nf / mf;
            mf = 1;
        }
    }
    return nf / mf;
}

public int jumpFloor(int number)
{
    int ret = 1;
    int count = number / 2;
    for (int i = 1; i <= count; i++)
    {
        ret += c(number - i, i);
    }
    return ret;
}

给TA打赏
共{{data.count}}人
人已打赏
随笔日记

wdmsh:特殊服务器,无视任何投诉,1Gbps带宽,不限流量,可以扫描/网络测试/邮件群发等

2020-11-9 4:42:30

随笔日记

使用 Docker 在 Linux 上托管 ASP.NET Core 应用程序

2020-11-9 4:42:32

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索