【复习16-18天】【我们一起60天准备考研算法面试（大全）-第二十四天 24/60】

**复习16-18天**

**我们一起60天准备考研算法面试（大全）-第二十四天24/60**

---

## 前言在前几天的基础上，我们继续深入学习算法相关知识。今天，我们将重点讲解动态规划和贪心算法。

## 动态规划###什么是动态规划？

动态规划（Dynamic Programming）是一种解决复杂问题的方法，通过分解问题为更小的子问题，并且每个子问题只求解一次，以避免重复计算，从而提高效率。

### 动态规划的步骤1. **分解问题**：将原来的问题分解为多个子问题，每个子问题都有明确的答案。
2. **递归关系**：每个子问题之间存在递归关系，通过解决一个子问题可以得到另一个子问题的答案。
3. **存储结果**：为了避免重复计算，每个子问题的答案都需要被存储起来，以便下一次使用。

### 动态规划的例子####1.斐波那契数列斐波那契数列是一个经典的动态规划问题。斐波那契数列的第 n 个数字是前两个数字之和。

def fibonacci(n):
 if n <=0:
 return "Input should be a positive integer."
 elif n ==1:
 return0 elif n ==2:
 return1 else:
 fib_list = [0,1]
 for i in range(2, n):
 fib_list.append(fib_list[i-1] + fib_list[i-2])
 return fib_list[-1]

print(fibonacci(10)) # Output:34

####2.最长上升子序列最长上升子序列（Longest Increasing Subsequence，LIS）是动态规划的一个经典例子。给定一个整数数组，找出其中最长的上升子序列。

def longest_increasing_subsequence(nums):
 if not nums:
 return0 dp = [1] * len(nums)
 for i in range(1, len(nums)):
 for j in range(i):
 if nums[i] > nums[j]:
 dp[i] = max(dp[i], dp[j] +1)

 return max(dp)

print(longest_increasing_subsequence([10,9,2,5,3,7,101,18])) # Output:4

## 贪心算法###什么是贪心算法？

贪心算法（Greedy Algorithm）是一种解决问题的方法，通过在每一步中选择最优解，以求得全局最优解。

### 贪心算法的步骤1. **确定目标**：明确需要解决的问题。
2. **选择最优解**：在每一步中选择最优解，以求得全局最优解。
3. **避免局部最优**：避免陷入局部最优解，导致全局最优解无法实现。

### 贪心算法的例子####1. Activity Selection Problem活动选择问题（Activity Selection Problem）是贪心算法的一个经典例子。给定一个活动列表和开始时间列表，找出可以参加的最大活动数量。

def activity_selection(start, end):
 if not start or not end:
 return0 activities = []
 current_end = start[0]
 for i in range(1, len(start)):
 if start[i] >= current_end:
 activities.append((start[i], end[i]))
 current_end = end[i]

 return activitiesprint(activity_selection([1,3,2,5,7,8,10], [4,7,6,9,12,13,15]))# Output: [(1,4), (5,7), (8,13)]

## 总结在本文中，我们学习了动态规划和贪心算法的基本概念、步骤和例子。通过理解这些算法，能够更好地解决复杂问题，并且提高效率。

---

**下一篇文章将继续讲解其他算法相关知识。**

---

## 附注本文中的代码示例仅供参考，可能需要根据具体场景进行调整和优化。

如果您有任何疑问或建议，请在评论区留言，我们将尽快回复。