递归题解

Posted by 周思进 on July 11, 2020

这周在极客时间上将递归相关的专栏文章都学习看了下,其中《数据结构与算法之美》专栏中的文章觉得很受用。

文章归纳了对于一个题解是否适合递归方式去解决,我个人学习后总结为满足如下两个条件即可:
1、这个问题能否转成数据规模更小的问题,但问题的本质实际是一样的,即解题思路还是一样
2、是否存在终止提交

所以写递归的关键是要找到如何将大问题转化成小问题的方法,以此来写出递推公式,然后再推敲终止条件,最后转化成实际代码。

在实现的过程中,不要在脑子里想你写的这个递归代码具体是怎么在一层层调用的,不要去想就行了。想明白你当前将问题转化为小问题的方式是否正确即可。

下面做了一些递归问题(当然很多问题递归不是最优解),只能说我还是得多练练啊…


一、leetcode 70 爬楼梯问题

问题:走楼梯可以走1步或者走2步,求n阶台阶存在的n种走法

思路:
1、只有1个台阶,则只有1种走法
2、2个台阶,则有2种走法
3、3个台阶,有 1+1+1,1+2,2+1 , 共3种走法
4、4个台阶,有 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 共5种走法

通过数学归纳法会发现,有3个台阶的时候是前两个台阶走法之和,4个台阶同样是前两个台阶走法之和 推出递推公式: f(n) = f(n-1) + f(n-2) (实际就是斐波那契数列问题)

换个思路思考:到达n阶台阶,最后走法就两种,要么是1步,要么是2步,那么对应的总的走法也就是最后走1步前面的走法加上 最后是2步前面的走法之和,对应公式就是 f(n) = f(n-1) + f(n-2)

推敲终止条件:n = 0时,返回0, n = 1 时,返回1, n = 2 时,返回

代码实现:

class Solution:
    def climbStairs(self, n: int) -> int:
        if (n < 0):
            return 0
        if (n == 1):
            return 1
        if (n == 2):
            return 2

        ret = self.climbStairs(n-1) + self.climbStairs(n-2)
        return ret

结果递归题解方式超时了…

转成非递归实现:

class Solution:
    def climbStairs(self, n: int) -> int:
        num1 = 0
        num2 = 1
        sum = 0

        for i in range(n):
            sum = num1 + num2
            num1 = num2
            num2 = sum

        return sum

二、汉诺塔问题

有三根杆子A,B,C。A杆上有 N 个 (N>1) 穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆:
每次只能移动一个圆盘;
大盘不能叠在小盘上面。
提示:可将圆盘临时置于 B 杆,也可将从 A 杆移出的圆盘重新移回 A 杆,但都必须遵循上述两条规则。
问:如何移?最少要移动多少次

思路:
最后所有盘子都在C杆,盘子的顺序仍旧是跟A盘一样,则A盘最底下的那个盘子,需要放到C盘最下面,然后 再把A盘剩余的盘子放在这个最大的盘子上面。

则需要先把 n-1 个盘子放到 b 盘(当做辅助杆), 然后把剩余的一个大盘放到 C盘(当做目标杆),然后再把辅助杆上的 n-1 个盘子放到目标盘

对应公式就是:
move(n, from, to, buff) =
move(n-1, from, buff, to);
from->to;
move(n-1, buff, to, from);

终止条件则是只剩最后1个盘子了,从 from 移动到 to

代码实现:

void move(int n, char from, char to, char buff)
{
    if (1 == n)
    {
        printf("%c -> %c\n", from, to);
        return;
    }

    move(n-1, from, buff, to);
    printf("%c - > %c\n", from, to);
    move(n-1, buff, to, from);

    return ;
}

三、赏金问题

假设有四种面额的钱币,1 元、2 元、5 元和 10 元,而您一共给我10元, 那您可以奖赏我1张10元,或10张1元,或5张1元外加1张5元等等。 如果考虑每次奖赏的金额和先后顺序,那么最终一共有多少种不同的奖赏方式?

思路:
在数额大于0的情况下,你可以都有四种额度选择,所以你需要分别记录这四种选择的情况。
当选择其中一种方式后,也就是要对剩余额度继续处理,也就是转成了对应的小问题处理。
当剩余额度为0,即满足解题要求,输出记录中间选择的结果;当剩余额度小于0,则直接返回,丢弃此次选择。

代码实现:

money = [1, 2, 5, 10]

def choice_money(result:list, remain):
    if (remain == 0):
        print(result)
        return 

    if (remain < 0):
        return 

    for i in range(len(money)):
        newresult = result[::]
        newresult.append(money[i])
        choice_money(newresult, remain-money[i])

四、整数乘积

一个整数可以被分解为多个整数的乘积,例如,6 可以分解为 2x3。请使用递归编程的方法,为给定的整数 n,找到所有可能的分解(1 在解中最多只能出现 1 次)。例如,输入 8,输出是可以是 1x8, 8x1, 2x4, 4x2, 1x2x2x2, 1x2x4, ……

思路:
这个问题的思路基本就是照着第三题做的

def get(n:int, result:list):
    begin = 0
    if 1 in result:
        begin = 2
    else:
        begin = 1

    if (1 == n):
        if len(result) != 1:
            print(result)
        if 1 not in result:
            result.append(1)
            print(result)
        return

    for i in range(begin, n+1):
        if (n % i == 0):
            newresult = result[::]
            newresult.append(i)
            get(n // i, newresult)

五、麦子问题

你一定听说过这个故事。国王对发明国际象棋的大臣很佩服,问他要什么报酬,大臣说:请在第1个棋盘格放1粒麦子,在第2个棋盘格放2粒麦子,在第3个棋盘格放4粒麦子,在第4个棋盘格放8粒麦子,……后一格的数字是前一格的两倍,直到放完所有棋盘格(国际象棋共有64格)。 国王以为他只是想要一袋麦子而已,哈哈大笑。 当时的条件下无法准确计算,但估算结果令人吃惊:即使全世界都铺满麦子也不够用! 请你借助计算机准确地计算,到底需要多少粒麦子

思路:
当前格子的麦子数是前一个格子的麦子数的两倍,累加当前格子的麦子数即可。

实现代码如下:

def sum(n):
    res = 1
    if (n == 1):
        return 1

    ret = 2 * sum(n-1)
    res += ret

    return res

六、阶乘n!计算

def factorial(n):
    if (1 == n):
        return 1

    n = n * factorial(n-1)
    return n