简单暴力到dp的优化（萌新篇）

小灰灰 2022-05-26 21:05 172阅读 0赞

**想写一系列文章，总结一些题目，看看解决问题、优化方法的过程到底是什么样子的。**

# **系列问题一：斐波那契数列问题** #

**在数学上，斐波纳契数列以如下被以[递归][Link 1]的方法定义：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N\*）根据定义，前十项为1, 1, 2, 3, 5, 8, 13, 21, 34, 55**

# **问题一：** #

**给定一个正整数n，求出斐波那契数列第n项（这时n较小）**

**解法一：最笨，效率最低，暴力递归，完全是抄定义。请看代码**

def f0(n):
        if n==1 or n==2:
            return 1
        return f(n-1)+f(n-2)

***分析一下，为什么说递归效率很低呢？咱们来试着运行一下就知道了：***

***比如想求f(10)，计算机里怎么运行的？***

***![20180412131244538][]***

**每次要计算的函数量都是指数型增长，时间复杂度O(2^(N/2))<=T(N)<=O(2^N),效率很低。效率低的原因是，进行了大量重复计算，比如图中的f(8),f(7).....等等，你会发现f(8)其实早就算过了，但是你后来又要算一遍。**

**如果我们把计算的结果全都保存下来，按照一定的顺序推出n项，就可以提升效率，斐波那契（所有的一维）的顺序已经很明显了，就是依次往下求。。**

# **优化1** #

def f1(n):
        if n==1 or n==2:
            return 1
        l=[0]*n
        l[0],l[1]=1,1
        for i in range(2,n):
            l[i]=l[i-1]+l[i-2]
        return l[-1]

**时间复杂度o(n)，依次往下打表就行，空间o(n).**

**继续优化：既然只求第n项，而斐波那契又严格依赖前两项，那我们何必记录那么多值呢？记录前两项就行了**

# ***优化2*** #

def f2(n):
        a,b=1,1
        for i in range(n-1):
            a,b=b,a+b
        return a

**此次优化做到了时间o(n),空间o(1)**

**附：这道题掌握到这里就可以了，但是其实有时间o(log2n)的方法**

# **优化三：** #

**学习过线性代数的同学们能够理解：**

***![20180412131342475][]***

**结合快速幂算法，我们可以在o(log2n)内求出某个对象的n次幂。(在其它专题详细讲解)**

**注意：只有递归式不变，才可以用矩阵+快速幂的方法。**

**注：优化三可能只有在面试上或竞赛中用，当然，快速幂还是要掌握的。**

**经过这个最简单的斐波那契，大家有没有一点感觉了？**

**好，我们继续往下走**

**(补充：pat、蓝桥杯原题，让求到一万多位，结果模一个数。**

**可以每个结果都对这个数取模，否则爆内存，另：对于有多组输入并且所求结果类似的题，可以先求出所有结果存起来，然后直接接受每一个元素，在表中查找相应答案)**

# **问题二：** #

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

**依旧是找递推关系，分析：跳一阶，就一种方法，跳两阶，它可以一次跳两个，也可以一个一个跳，所以有两种，三个及三个以上，假设为n阶，青蛙可以是跳一阶来到这里，或者跳两阶来到这里，只有这两种方法。它跳一阶来到这里，说明它上一次跳到n-1阶，同理，它也可以从n-2跳过来，f（n）为跳到n的方法数，所以，f(n)=f(n-1)+f(n-2)**

**和上题的优化二类似。**

**因为递推式没变过，所以可以用优化三**

# **问题三：** #

**我们可以用2\*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2\*1的小矩形无重叠地覆盖一个2\*n的大矩形，总共有多少种方法？提示，大矩形看做是长度吧**

**请读者自己先思考一下吧。。。仔细看题。。仔细思考**

**如果n是1，只有一种，竖着放呗；n是2，两种：**

***![20180412131548799][]，***

***n等于3，三种：***

***![20180412131559549][]***

**题意应该理解了吧？**

**读到这里，你们应该能很快想到，依旧是斐波那契式递归啊。**

**对于n>=3:怎么能覆盖到三？只有两种办法，从n-1的地方竖着放了一块，或者从n-2的位置横着放了两块呗。**

**和问题二的代码都不用变。**

# **问题四：** #

**给定一个由0-9组成的字符串，1可以转化成A，2可以转化成B。依此类推。。25可以转化成Y，26可以转化成z，给一个字符串，返回能转化的字母串的有几种？**

**比如：123，可以转化成**

**1 2 3变成ABC，**

**12 3变成LC，**

**1 23变成AW，三种，返回三，**

**99999，就一种：iiiii，返回一。**

**分析：求i位置及之前字符能转化多少种。**

**两种转化方法，一，字符i自己转换成自己对应的字母，二，和前面那个数组成两位数，然后转换成对应的字母**

**假设遍历到i位置，判断i-1位置和i位置组成的两位数是否大于26，大于就没有第二种方法，f(i)=f(i-1),想反，等于f(i-1)+f(i-2)**

**注意：递归式不确定，不能用矩阵快速幂**

**(这几个题放到这里就是为了锻炼找递归关系的能力，不要只会那个烂大街的斐波那契)**

'''
    斐波那契问题：
    斐波纳契数列以如下被以递归的方法定义：
    F(1)=1
    F(2)=1
    F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）
    '''
    #暴力抄定义,过多重复计算
    def f0(n):
        if n==1 or n==2:
            return 1
        return f(n-1)+f(n-2)
    #记录结果后依次递推的优化，时间O(N)
    def f1(n):
        if n==1 or n==2:
            return 1
        l=[0]*n
        l[0],l[1]=1,1
        for i in range(2,n):
            l[i]=l[i-1]+l[i-2]
        return l[-1]
    #既然严格依赖前两项，不必记录每一个结果，优化空间到O(1)
    def f2(n):
        a,b=1,1
        for i in range(n-1):
            a,b=b,a+b
        return a

[Link 1]: https://baike.baidu.com/item/%E9%80%92%E5%BD%92
[20180412131244538]: /images/20220527/a210d4c30fdc4e32ae0a30a85cdea0b6.png
[20180412131342475]: /images/20220527/ce91d5aa9e794e6a943bbba8c667fdff.png
[20180412131548799]: /images/20220527/284fd2096db348479738931be361aef2.png
[20180412131559549]: /images/20220527/dd9dddd5fa1244e38e60afff3ea6b885.png