斐波拉契数列

1,1,2,3,5,8,13...,状态转移方程:

暴力递归

def main(a):
    if a == 1 or a == 2:
        return 1
    return main(a-1) + main(a-2)

时间复杂度为O(2^n),有如下递归树:

我们可以看到许多的计算都重复了,例如下面的f(18)等,那么如何避免这个问题呢?有效的方法就是将第一次计算出的f(18)的结果保留下来,如果下次再计算到这个f(18)的时候直接将结果取出来即可,简称备忘录方法,如下:

带备忘录的递归解法

memo = dict()
def main(a):
    if a == 1 or a == 2:
        return 1
    if a in memo:
        return memo[a]
    memo[a] = main(a-1) + main(a-2)
    return main(a-1) + main(a-2)

DP table解法

自底向上优化

dp = []
def main(a):
    if a == 1 or a == 2:
        return 1
    dp.append(1)
    dp.append(1)
    for i in range(2, a):
        dp.append(dp[i - 1] + dp[i - 2])
    return dp[a-1]

原理图如下(emmmmm,图是搬运过来的,所以前面的第0位还是用到了的,往前移一位就行了)

优化

再进行空间复杂度的优化

def main(a):
    if a == 1 or a == 2:
        return 1
    prev = 1
    curr = 1
    for i in range(3, a + 1):
        num = prev + curr
        prev = curr
        curr = num
    return curr

由原来的时间复杂度O(2^n)变为了O(n),空间复杂度降为O(1)

凑零钱问题

假设给你k中面值的硬币,面值分别为c1,c2,c3 ... ck,每种硬币的数量无限,再给一个总金额amount,问最少需要几枚硬币凑出这个金额,如果不可能凑出,则返回-1

状态转移方程:

暴力递归

def coinChange(coins, amount):
    def main(n):
        if n == 0:  # 当n - coin = 0 的时候说明这条路走的通
            return 0
        if n < 0:  # 当n - coin < 0 的时候则说明这条路走不通
            return -1
        res = float("INF")  # float("INF")为正无穷大,负无穷大则为float("-INF")
        for coin in coins:  # 递归列表
            sub = main(n - coin)  # 取出一个值n就要减去那个值
            if sub == -1:
                continue  # 当main函数的返回值为-1的时候,这条路走不通,则挑出循环
            res = min(res, 1 + sub)  # 当到了树的最低下,上面的if语句没有执行跳出去,则使res=sub+1
        return res if res != float("INF") else -1  # 这条路走的通,则返回res的值给sub,结合上面的一条语句进行计数

    return main(amount)


# 最后取出第一个选择的那个数字的时候计算出的res最小值,然后再把每个数字的最小值拿出来比较得出最终的最小值
if __name__ == "__main__":
    print(coinChange([1, 2, 5], 11))

以上的路走的通的意思是能够凑出这些硬币,递归图如下:

带备忘录的递归解法

def coinChange(coins, amount):
    memo = dict()

    def main(n):
        if n in memo:  # 查找备忘录,避免重复计算,就是计算以上颜色相同的部分
            return memo[n]
        if n == 0:
            return 0
        if n < 0:
            return -1
        res = float("INF")
        for coin in coins:
            sub = main(n - coin)
            if sub == -1:
                continue
            res = min(res, 1 + sub)
        memo[n] = (res if res != float("INF") else -1)
        return memo[n]

    return main(amount)

if __name__ == "__main__":
    print(coinChange([1, 2, 5], 11))

DP table解法

def main(coins, a):
    for i in range(a + 1):
        dp.append(i)
    for i in range(a + 1):
        for coin in coins:
            if i - coin < 0:
                continue
            dp[i] = min(dp[i], 1 + dp[i - coin])
    return -1 if dp[a] == (a + 1) else dp[a]

if __name__ == "__main__":
    dp = []
    print(main([1, 2, 5], 11))

演示图如下:

借用大佬的一句话:

计算机解决问题其实没有任何奇技淫巧,他唯一的解决方法就是穷举,穷举所有的可能性。算法设计无非就是先思考“如何穷举”,然后再追求“如何聪明的穷举”

最长递增子序列

动态规划解法

动态规划的核⼼设计思想是数学归纳法。

假设当结论在k<n的时候成立,然后想办法证明k=n的时候结论也成立,如果能够证明的出来,那么就说明这个结论对于任何数都成立,再看到这个题目,假如我们能够证明,最后一个nums[i]的值大于前一个nums[j]的值,那么就能够证明出他和nums[j]所构成的最长递增子序列能够结合,随后再将长度加一,且将nums[i]加入到这个最长递增子序列中,即:

代码实现

def main(nums):
    res = 0
    dp = []  # 定义每一位数的最长递增子序列
    for i in range(len(nums)):
        dp.append(1)  # 令每一位的初始值为1

    for i in range(len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)  # dp[i]表示nums[i]这个数结尾的最长递增子序列的长度

    for i in range(len(dp)):
        res = max(res, dp[i])
    return res

if __name__ == "__main__":
    print(main([8, 7, 10]))

可见时间复杂度为O(n^2)

二分查找解法

将输入的序列分成若干堆,需要遵循以下规则:

只能把小的数字压到比它大的数字上,也就是用小的数字覆盖掉原来大的,那么如何去压呢?那么就看该数字该如何选择了,如果当前数字较大没有可以放置的堆,那么就在边上新建一个堆,再把数字放进去,如果有多个堆可以选择,则选择这多个堆中考最左边的位置,保证堆顶的数字是有序的了,就像这样(A是最大的)

这样堆顶的数字就可以形成一个最长递增子序列,当然序列肯定不止一个,如下:

能够保证得出最长递增子序列,随后在查找该放在哪个堆的时候使用二分法查找就可以提高效率,代码如下:

def main(nums):
    piles = 0  #定义最长递增子序列的长度
    top = []  # 定义每一位数的最长递增子序列
    for i in range(len(nums)):
        top.append(0)  # 令每一位的初始值为1
    for i in range(len(nums)):
        poker = nums[i]
        left = 0
        right = piles
        while left < right:
            mid = int((left + right) / 2)
            if top[mid] > poker:
                right = mid
            elif top[mid] < poker:
                left = mid + 1
            else:
                right = mid
        if left == piles:
            piles += 1  # 最长递增子序列的长度加一
        top[left] = poker
    return piles

if __name__ == "__main__":
    print(main([8, 7, 6, 1, 4, 10]))

编辑距离

先来看一下题目描述

递归解法

def minDistance(s1, s2):
    def dp(i, j):
        if i == -1:
            return j + 1  # 假如当s1字符串循环i次循环完了,j还有剩下的部分就直接全部进行一个操作j+1次即可,因为还剩下j+1个字符
        if j == -1:
            return i + 1  # 同上

        if s1[i] == s2[j]:
            return dp(i - 1, j - 1)  # 若相等直接跳过进行下一个字符的判断
        else:
            return min(dp(i, j - 1) + 1,  # 插入
                       dp(i - 1, j - 1) + 1,  # 替换
                       dp(i - 1, j) + 1)  # 删除

    return dp(len(s1) - 1, len(s2) - 1)

if __name__ == "__main__":
    print(minDistance("apple", "add"))

以上是将appleadd两个字符串进行转换,得出的结果为4,即所需操作的最小值

带备忘录的递归解法

def minDistance(s1, s2):
    memo = dict()  # 备忘录

    def dp(i, j):
        if (i, j) in memo:
            return memo[(i, j)]
        if i == -1:
            return j + 1  # 假如当s1字符串循环i次循环完了,j还有剩下的部分就直接全部进行一个操作j+1次即可,因为还剩下j+1个字符
        if j == -1:
            return i + 1  # 同上

        if s1[i] == s2[j]:
            memo[(i, j)] = dp(i - 1, j - 1)  # 若相等直接跳过进行下一个字符的判断
        else:
            memo[(i, j)] = min(dp(i, j - 1) + 1,  # 插入
                               dp(i - 1, j - 1) + 1,  # 替换
                               dp(i - 1, j) + 1)  # 删除
        return memo[(i, j)]
    return dp(len(s1) - 1, len(s2) - 1)


if __name__ == "__main__":
    print(minDistance("apple", "add"))

DP table解法

自底向上

首先确定dp数组的含义,dp数组是一个二维数组,如下:

dp[i][j]存储着s1[i]s2[j]的最小编辑距离,各相邻的数据之间有如下关系:

于是就可以写出以下代码:

def minDistance(s1, s2):
    m = len(s1)
    n = len(s2)
    dp = dict()
    dp[(0, 0)] = 0
    for i in range(1, m + 1):
        dp[(i, 0)] = i
    for i in range(1, n + 1):
        dp[(0, i)] = i
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[(i, j)] = dp[(i - 1, j - 1)]
            else:
                dp[(i, j)] = min(dp[(i, j - 1)] + 1,
                                 dp[(i - 1, j - 1)] + 1,
                                 dp[(i - 1, j)] + 1)
    return dp[(m, n)]


if __name__ == "__main__":
    print(minDistance("apple", "add"))

随后还可以将步骤推出来:

def minDistance(s1, s2):
    m = len(s1)
    n = len(s2)
    dp = dict()
    a = dict()  # 记录每一步的操作 0:啥都不做,1:插入,2:替换,3:删除
    dp[(0, 0)] = 0
    a[(0, 0)] = 0
    for i in range(1, m + 1):
        dp[(i, 0)] = i
        a[(i, 0)] = 3
    for i in range(1, n + 1):
        dp[(0, i)] = i
        a[(0, i)] = 1
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[(i, j)] = dp[(i - 1, j - 1)]  # 不动,也就是相同直接跳过 0
                a[(i, j)] = 0
            else:
                dp[(i, j)] = min(dp[(i, j - 1)] + 1,  # 插入 1
                                 dp[(i - 1, j - 1)] + 1,  # 替换 2
                                 dp[(i - 1, j)] + 1)  # 删除 3

            if dp[(i, j)] == dp[(i, j - 1)] + 1:
                a[(i, j)] = 1
            elif dp[(i, j)] == dp[(i - 1, j - 1)] + 1:
                a[(i, j)] = 2
            elif dp[(i, j)] == dp[(i - 1, j)] + 1:
                a[(i, j)] = 3
    for i in range(n + 1):
        for j in range(m + 1):
            print(a[(j, i)], end="")
        print()
    return dp[(m, n)]


if __name__ == "__main__":
    print(minDistance("apple", "add"))

以上代码将输出:

033333
103333
112222
111222
4

从后面往前推就行,0,2代表对角(跳过/替换),1代表向上(插入),3代表向左(删除)

寻找到0的最佳捷径就OK

高楼扔鸡蛋

题目:

目前有一栋1到NN层的楼,然后给你K鸡蛋(K至少为1),现在确定这栋楼存在楼层0<=F<=N,在这层楼将鸡蛋扔下去鸡蛋恰好没有碎(高于F的楼层都会碎,低于F的楼层都不会碎),现在问,最坏的情况下,你至少要扔多少次鸡蛋,才能确定这个楼层F

带备忘录的递归解法

def main(K, N):  # K个鸡蛋,N层楼
    memo = dict()
    if K == 0:
        return N
    if N == 0:
        return 0
    if (K, N) in memo:
        return memo[(K, N)]
    res = float("INF")
    for i in range(1, N + 1):
        res = min(res, max(main(K - 1, i - 1), main(K, N - i)) + 1)  # 在max最坏的情况下,求min最优解,main(K - 1, i - 1)表示碎了,main(K, N - i)表示没碎
    memo[(K, N)] = res
    return res


if __name__ == "__main__":
    print(main(1, 100))

二分法优化

def main(K, N):  # K个鸡蛋,N层楼
    memo = dict()
    if K == 0:
        return N
    if N == 0:
        return 0
    if (K, N) in memo:
        return memo[(K, N)]
    res = float("INF")
    lo = 1
    hi = N
    while lo <= hi:
        mid = (lo + hi) // 2
        broken = main(K - 1, mid - 1)  # 碎
        not_broken = main(K, N - mid)  # 没碎
        # res = min(max(碎, 没碎) + 1)
        if broken > not_broken:
            hi = mid - 1
            res = min(res, broken + 1)
        else:
            lo = mid + 1
            res = min(res, not_broken + 1)
    memo[(K, N)] = res
    return res

if __name__ == "__main__":
    print(main(1, 100))

未完待续。。。