4、 贪心
4.1思想
贪心算法思想：
贪心算法是一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法。
核心性质：
贪心算法的核心性质是局部最优解能决定全局最优解。这意味着在每个决策步骤中，选择当前看起来最优的选择，最终能够导致整个问题的最优解。
适用条件：
如果问题具有贪心选择性质，即局部最优解能导致全局最优解，那么可以采用贪心算法来求解。
4.2例子
贪心算法的局限性：
并不是所有问题采用局部最优都能得到全局最优解。例如，如果硬币面值改为1元、2元、4元、5元、6元，支付9元时，贪心算法可能会选择6+2+1，需要3枚硬币，但最优解是4+5，只需要2枚硬币。
4.3例题
https://www.lanqiao.cn/problems/545
import heapq
# 读取输入的数字个数
n = int(input())
# 读取数字并转换为整数列表
a = list(map(int, input().split()))
# 将列表转换为堆
heapq.heapify(a)
# 初始化答案变量
ans = 0
# 当堆中元素个数大于1时，执行循环
while len(a) != 1:
# 弹出堆中的两个最小元素
x = heapq.heappop(a)
y = heapq.heappop(a)
# 将两个元素的和放回堆中
heapq.heappush(a, x + y)
# 累加答案
ans += x + y
# 打印最终答案
print(ans)
5、 模拟
5.1概述
模拟题：这类题目通常要求你根据题目的描述来模拟一个过程或系统，而不是解决一个算法问题。
注意点：
读懂题：在编程之前，首先要彻底理解题目的要求和流程。
代码和步骤一一对应：编写的代码应该与解题步骤紧密对应，包括变量名、函数名以及每个函数的功能都应该清晰明确。
提取重复的部分：在编程过程中，如果发现有重复的代码块，应该将其提取出来，写成独立的函数或子模块，以提高代码的可读性和可维护性。
按顺序写，分块调试：按照逻辑顺序编写代码，并在完成每个部分后进行调试，确保每个模块都能正确运行。
5.2例题
n = int(input())
ans = n
while n >= 3:
n -= 3
ans += 1
n += 1
print(ans)
从用户那里获取一个整数输入n
初始化ans为n的值
当n大于或等于3时，执行循环：
从n中减去3
将ans增加1
将n增加1
循环结束后，打印ans的值
n = int(input())
ans = n
while n >= 3:
ans += n // 3
n = n // 3 + n % 3
print(ans)
从用户那里获取一个整数输入n
初始化ans为n的值
当n大于或等于3时，执行循环：
将ans增加n除以3的整数部分（n // 3）
更新n为n除以3的整数部分加上n除以3的余数（n % 3）
循环结束后，打印ans的值
6、 二分（查找）
二分的关键除了运用模板，还要通过题意写对check函数，来作为判断下一个区间的条件
6.1概述
二分法：这是一种在有序数组中查找特定元素的搜索算法。它通过比较数组中间元素和目标值来工作。如果中间元素正好是目标值，则搜索结束。如果目标值小于中间元素，则在数组的前半部分继续搜索；如果目标值大于中间元素，则在数组的后半部分继续搜索。这个过程重复进行，每次都将搜索范围缩小一半，直到找到目标值或搜索范围为空。
时间复杂度：二分查找算法的时间复杂度是O(log n)，其中n是数组中元素的数量。这是因为每次迭代都将搜索范围减半，所以需要的迭代次数是对数级别的。
前提条件：二分查找的前提是数组必须是有序的，且函数或数组的值具有单调性。单调性意味着数组中的元素要么全部是非递减的（升序），要么全部是非递增的（降序）。
核心：二分查找的核心思想是利用数组的单调性来调整搜索区间。通过比较中间元素和目标值，可以确定目标值位于中间元素的哪一侧，从而缩小搜索范围。
6.2例题
https://www.lanqiao.cn/problems/99
# 读取小朋友的数量K和巧克力的总块数N
N, K = map(int, input().split())
# 初始化一个列表a，用于存储每块巧克力的长和宽
a = []
# 循环N次，每次读取一块巧克力的长和宽，并存储在列表a中
for i in range(N):
x, y = map(int, input().split())
a.append((x, y))
# 二分查找 定义一个函数check(x)，用于判断边长为x时，能否切出至少K块正方形巧克力
def check(x):
# 初始化计数器cnt，用于统计切出的正方形巧克力块数
cnt = 0
# 遍历每块巧克力
for h, w in a:
# 对于每块巧克力，计算可以切出多少块边长为x的正方形巧克力
cnt += (h // x) * (w // x)
# 如果切出的巧克力块数大于等于K，返回True
return cnt >= K
# 初始化二分查找的左右边界，left为1，right为100000，ans为1，用于存储最大边长
left, right = 1, 100000
ans = 1
# 当左边界小于等于右边界时，进行二分查找
while left <= right:
# 计算中间值mid
mid = (left + right) // 2
# 如果check(mid)为True，说明边长为mid可以满足条件，尝试更大的边长
if check(mid):
ans = mid # 更新最大边长
left = mid + 1 # 更新左边界
else:
# 如果check(mid)为False，说明边长为mid不能满足条件，尝试更小的边长
right = mid - 1
# 输出最大边长
print(ans)
7、 DP（普通一维）
7.1解析
动态规划：是一种算法思想，用于解决具有重叠子问题和最优子结构特征的问题。
重叠子问题：在动态规划中，子问题是原问题的小版本。这意味着在解决原问题的过程中，相同的子问题会被重复计算多次。
最优子结构：在动态规划中，大问题的最优解包含小问题的最优解。这意味着通过解决小问题并存储它们的解，可以推导出大问题的最优解。
7.2例题
# 定义楼梯的最大级数N和模数MOD
N = 100010
MOD = 1000000007
# 读取楼梯的总级数n和坏了的台阶数m
n, m = map(int, input().split())
# 初始化vis数组，用于标记台阶是否损坏，0表示未损坏，1表示损坏
vis = [0] * N
# 初始化f数组，用于存储到达每级台阶的方案数
f = [0] * N
# 读取坏掉的台阶编号，并标记在vis数组中
X = list(map(int, input().split()))
for x in X:
vis[x] = 1 # 将坏掉的台阶编号对应的vis数组位置设为1
# 设置初始条件，第0级台阶有1种到达方式，第1级台阶的到达方式取决于它是否损坏
f[0] = 1
f[1] = 1 - vis[1]
# 动态规划计算到达每一级台阶的方案数
for i in range(2, n + 1):
# 如果当前台阶损坏，则跳过不计算
if vis[i]:
continue
# 如果当前台阶未损坏，计算到达该台阶的方案数，即前两级台阶方案数之和对MOD取模
f[i] = (f[i - 1] + f[i - 2]) % MOD
# 输出到达第n级台阶的方案数，对MOD取模的结果
print(f[n])