北大硕士LeetCode算法专题课--动态规划和贪心算法

谁借莪１个温暖的怀抱￠ 2024-03-29 14:24 63阅读 0赞

**面试专题课：**

[北大硕士LeetCode算法专题课--递归和回溯\_骨灰级收藏家的博客-CSDN博客][LeetCode_--_-CSDN]

[北大硕士LeetCode算法专题课-栈、队列相关问题\_骨灰级收藏家的博客-CSDN博客][LeetCode_-_-CSDN]

[北大硕士LeetCode算法专题课--链表相关问题\_骨灰级收藏家的博客-CSDN博客][LeetCode_--_-CSDN 1]

[北大硕士LeetCode算法专题课-查找相关问题\_骨灰级收藏家的博客-CSDN博客][LeetCode_-_-CSDN 1]

[北大硕士LeetCode算法专题课-字符串相关问题\_骨灰级收藏家的博客-CSDN博客][LeetCode_-_-CSDN 2]

[北大硕士LeetCode算法专题课-数组相关问题\_骨灰级收藏家的博客-CSDN博客][LeetCode_-_-CSDN 3]

[北大硕士LeetCode算法专题课-基础算法查找\_骨灰级收藏家的博客-CSDN博客][LeetCode_-_-CSDN 4]

[北大硕士LeetCode算法专题课-基础算法之排序\_骨灰级收藏家的博客-CSDN博客][LeetCode_-_-CSDN 5]

[北大硕士LeetCode算法专题课---算法复杂度介绍\_骨灰级收藏家的博客-CSDN博客][LeetCode_---_-CSDN]

**什么是动态规****划**

我们以斐波那契数列为例来说明什么是动态规划

斐波那契数列（Fibonacci sequence）: F(0)=0，F(1)=1, F(n)=F(n \- 1)+F(n \- 2)

import time
    def fib(n):
    if n == 0:
    return 0
    if n == 1:
    return 1
    return fib(n - 1) + fib(n - 2)
    
    if  		name 	 == ' 	main 	':  t1 = time.time()
    n = fib(10)
    t2 = time.time()
    print("n = %d, 用时%d 毫秒" % (n, (t2 - t1) * 1000))

![33f624ca731d4525be5d2770e58bacda.png][]

![ace45840827640ebb8a9c9feefd78d7d.png][]

![5dcefa53634c499d97c2c65ba65ff73c.png][]

![a6ec241116874be1a2ee326790d56c0b.png][]

![62bc0ab2ddf34812b06f3b0acecaa3d2.png][]

斐波那契数列，优化： 记忆化搜索

def fib2(n):
    global num  num += 1  if n == 0:
    return 0
    if n == 1:
    return 1
    if res[n] == -1:
    res[n] = fib2(n - 1) + fib2(n - 2)
    return res[n]
    if 	name	== ' 	main 	':
    res = [-1 for i in range(41)]  t1 = time.time()
    n = fib2(40)
    t2 = time.time()
    print("n = %d, 用时%d 毫秒,执行了%d次" % (n, (t2 - t1) * 1000, num))

记忆化搜索：自上向下的解决问题

def fib2(n):
    global num  num += 1  if n == 0:
    return 0
    if n == 1:
    return 1
    if res[n] == -1:
    res[n] = fib2(n - 1) + fib2(n - 2)
    return res[n]

动态规划：把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，在解决小问题的时候， 记忆每一个小问题的答案，使得每个小问题只解决一次，最终达到解决原问题的效果。

![5e82af8d1da3472599cc69de94edde99.png][]**爬楼梯** **(LeetCode** **70)**

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？提示：1 <= n <= 45

![f1063f6f7b9d4173a0d1750fabe67f31.png][]

解题思路：假设f(n) 表示爬 n 阶楼梯可能的走法。

自顶向下的思路： 假设当前站在第n阶楼梯上，那么上一步可能在第n-1 或者 n-2 阶, 分别需要爬1级台阶和2级台阶 所以 f(n) = f(n-1) \+ f(n-2)

代码实现1 暴力搜索 上面式子中 n-2>=0 所以 最后一次递归调用为 f(2) = f(1) \+ f(0)，边界就是 **f(1)** **=** **1****，****f(0)** **=** **1**

def climbStairs(n):
    if n == 0 or n == 1:
    return 1
    return climbStairs(n - 1) + climbStairs(n - 2)

代码实现2 记忆化搜索

def climbStairs2(n):  def dfs(i, memo):
    if i == 0 or i == 1:
    return 1
    if memo[i] == -1:
    memo[i] = dfs(i - 1, memo) + dfs(i - 2, memo)
    return memo[i]
    
    return dfs(n, [-1] * (n + 1))

代码实现3 动态规划

def climbStairs3(n):  res = [0] * (n + 1)  res[0] = res[1] = 1
    for i in range(2, n + 1):
    res[i] = res[i - 1] + res[i - 2]
    return res[-1]

**整数拆分** **(LeetCode** **343)**

假设给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。 返回 你可以获得的最大乘积 。2 <= n <= 58

![762b1b7c450b4121bbbef3b337875857.png][]

![8d7346b3987e40178369e15974ef23dd.png][]

![b128e74082954c8ca964fd8ee8c2f207.png][]

![a2c6864d9b2d4bf7b057df9e5d6c0cbe.png][]

![f960e0b047f5408fb211465cf02fbfd8.png][]

def integerBreak(n):  def dfs(n, memo):
    if n ==1:
    return 1
    if memo[n] !=-1:  return memo[n]
    res = -1
    for i in range(1,n):
    res = max(res,i*(n-i),i*dfs(n-i,memo))  memo[n] = res
    return res
    return dfs(n,[-1] * (n + 1))

def integerBreak(n):  dp = [0] * (n + 1)
    for i in range(2, n + 1):
    for j in range(i):
    dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
    return dp[n]

**打家劫****舍** **(LeetCode** **198)**

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是 相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

![a638c204be4d490ba96c4560e9a561ea.png][]

先考虑最简单的情况。如只有一间房屋，则偷窃该房屋，可以偷到最高总金额。如只有两间房屋，则由于两间房屋相邻， 不能同时偷窃，只能偷窃其中的一间房屋，因此选择其中金额较高的房屋进行偷窃，可以偷窃到最高总金额。

如果房屋数量大于两间，应该如何计算能够偷窃到的最高总金额呢？

对于第 k (k>2) 间房屋，有两个选项：

l 偷窃第 k 间房屋，那么就不能偷窃第 k-1 间房屋，偷窃总金额为前 k-2 间房屋的最高总金额与第 k 间房屋的金额之和。

l 不偷窃第 k 间房屋，偷窃总金额为前 k-1 间房屋的最高总金额。

在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前 k 间房屋能偷窃到的最高总金额。 用 dp\[i\] 表示前 i 间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：

![a3efa07b044d486d823a12a2a9ed93b5.png][]

def rob(nums):  if not nums:
    return 0
    
    size = len(nums)
    if size == 1:
    return nums[0]
    
    dp = [0] * size  dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i in range(2, size):
    dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
    
    return dp[size - 1]

**发饼干** **(LeetCode** **455)**

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g\[i\]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s\[j\] 。 如果 s\[j\] >= g\[i\]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。

你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

![b21f212349ec4dbe866ddab6fa000a7c.png][]

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择，就能得到问题的答案。贪心 算法需要充分挖掘题目中条件，没有固定的模式，解决有贪心算法需要一定的直觉和经验。

为了尽可能满足最多数量的孩子，从贪心的角度考虑，应该按照孩子的胃口从小到大的顺序依次满足每个孩子，且 对于每个孩子，应该选择可以满足这个孩子的胃口且尺寸最小的饼干。

首先对数组 g 和 s 排序，然后从小到大遍历 g 中的每个元素，对于每个元素找到能满足该元素的 s 中的最小的元素。 具体而言，令 i 是 g 的下标，j是 s 的下标，初始时 i 和 j 都为 0，进行如下操作。

对于每个元素 g\[i\]，找到未被使用的最小的 j 使得 g\[i\]≤s\[j\]，则 s\[j\] 可以满足 g\[i\]。由于 g 和 s 已经排好序，因此整个过 程只需要对数组 g 和 s 各遍历一次。当两个数组之一遍历结束时，说明所有的孩子都被分配到了饼干，或者所有的 饼干都已经被分配或被尝试分配（可能有些饼干无法分配给任何孩子），此时被分配到饼干的孩子数量即为可以满 足的最多数量。

def findContentChildren(g, s):  g.sort()
    s.sort()
    n, m = len(g), len(s)  i = j = count = 0

[LeetCode_--_-CSDN]: https://blog.csdn.net/JACK_SUJAVA/article/details/128654973?spm=1001.2014.3001.5501
[LeetCode_-_-CSDN]: https://blog.csdn.net/JACK_SUJAVA/article/details/128645069?spm=1001.2014.3001.5501
[LeetCode_--_-CSDN 1]: https://blog.csdn.net/JACK_SUJAVA/article/details/128644105?spm=1001.2014.3001.5501
[LeetCode_-_-CSDN 1]: https://blog.csdn.net/JACK_SUJAVA/article/details/128643573?spm=1001.2014.3001.5501
[LeetCode_-_-CSDN 2]: https://blog.csdn.net/JACK_SUJAVA/article/details/128642376?spm=1001.2014.3001.5501
[LeetCode_-_-CSDN 3]: https://blog.csdn.net/JACK_SUJAVA/article/details/128626964?spm=1001.2014.3001.5501
[LeetCode_-_-CSDN 4]: https://blog.csdn.net/JACK_SUJAVA/article/details/128625648?spm=1001.2014.3001.5501
[LeetCode_-_-CSDN 5]: https://blog.csdn.net/JACK_SUJAVA/article/details/128624508?spm=1001.2014.3001.5501
[LeetCode_---_-CSDN]: https://blog.csdn.net/JACK_SUJAVA/article/details/128611560?spm=1001.2014.3001.5501
[33f624ca731d4525be5d2770e58bacda.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/bdadf06717474eae907040a16547d26d.png
[ace45840827640ebb8a9c9feefd78d7d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/d189382a93144a97a42d3bd09733a975.png
[5dcefa53634c499d97c2c65ba65ff73c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/12cf59d0d84d4daab3dd195d4d088c76.png
[a6ec241116874be1a2ee326790d56c0b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/68c063319541434ba9974a7c86ec924e.png
[62bc0ab2ddf34812b06f3b0acecaa3d2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/1a645b1d1060440192b1552d380ef4b6.png
[5e82af8d1da3472599cc69de94edde99.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/667da25fd83642ef9f7a58248059c15d.png
[f1063f6f7b9d4173a0d1750fabe67f31.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/5a1c6f5b99dd4c3e807ff7ca4f483c28.png
[762b1b7c450b4121bbbef3b337875857.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/9aa8c2922f0849119418910a6418a70d.png
[8d7346b3987e40178369e15974ef23dd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/72c3c3a34e104eaf91fc947c176eb4f7.png
[b128e74082954c8ca964fd8ee8c2f207.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/fc2422c0d39e4e78a0f458659dae1f62.png
[a2c6864d9b2d4bf7b057df9e5d6c0cbe.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/ac734448bbfa4cfa83baabd3fc063901.png
[f960e0b047f5408fb211465cf02fbfd8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/c1c38ed25e7d4da4904af884f6fe91eb.png
[a638c204be4d490ba96c4560e9a561ea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/789155c87f4e42af8bf19f3f8caee0a6.png
[a3efa07b044d486d823a12a2a9ed93b5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/3876c87bc49a46329402585d6371babd.png
[b21f212349ec4dbe866ddab6fa000a7c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/98d07d893cb847a384232e7fae25b211.png