字节跳动春招研发部笔试题
1.万万没想到之聪明的编辑
我叫王大锤，是一家出版社的编辑。我负责校对投稿来的英文稿件，这份工作非常烦人，因为每天都要去修正无数的拼写错误。但是，优秀的人总能在平凡的工作中发现真理。我发现一个发现拼写错误的捷径：
三个同样的字母连在一起，一定是拼写错误，去掉一个的就好啦：比如 helllo -> hello
两对一样的字母（AABB型）连在一起，一定是拼写错误，去掉第二对的一个字母就好啦：比如 helloo -> hello
上面的规则优先“从左到右”匹配，即如果是AABBCC，虽然AABB和BBCC都是错误拼写，应该优先考虑修复AABB，结果为AABCC
我特喵是个天才！我在蓝翔学过挖掘机和程序设计，按照这个原理写了一个自动校对器，工作效率从此起飞。用不了多久，我就会出任CEO，当上董事长，迎娶白富美，走上人生巅峰，想想都有点小激动呢！
……
万万没想到，我被开除了，临走时老板对我说： “做人做事要兢兢业业、勤勤恳恳、本本分分，人要是行，干一行行一行。一行行行行行；要是不行，干一行不行一行，一行不行行行不行。” 我现在整个人红红火火恍恍惚惚的……
请听题：请实现大锤的自动校对程序
数据范围： 1≤n≤50 1 \le n \le 50 \ 1≤n≤50 ，每个用例的字符串长度满足 1≤l≤1000 1 \le l \le 1000 \ 1≤l≤1000
输入描述:
第一行包括一个数字N，表示本次用例包括多少个待校验的字符串。后面跟随N行，每行为一个待校验的字符串。输出描述:
N行，每行包括一个被修复后的字符串。示例1
输入
2 helloo wooooooow输出
hello woow示例2
输入
1 nowcoder输出
nowcode
"""
1、问题分析：该题主要是对字符串的处理，难点在于如何对字符串进行删除，python里面是通过用list模拟栈来进行快速删除的，其实也可以看成简单模拟，代码很简单都能看懂
"""
def solve(s: str):res = []for char in s:res.append(char)if len(res) >= 3 and res[-1] == res[-2] == res[-3]:res.pop()if len(res) >= 4 and res[-1] == res[-2] and res[-3] == res[-4]:res.pop()return "".join(res)n = int(input())
for _ in range(n):s = input().strip()print(solve(s))
2.万万没想到之抓捕孔连顺
我叫王大锤，是一名特工。我刚刚接到任务：在字节跳动大街进行埋伏，抓捕恐怖分子孔连顺。和我一起行动的还有另外两名特工，我提议
我们在字节跳动大街的 N 个建筑中选定 3 个埋伏地点。
为了相互照应，我们决定相距最远的两名特工间的距离不超过 D 。
我特喵是个天才! 经过精密的计算，我们从X种可行的埋伏方案中选择了一种。这个方案万无一失，颤抖吧，孔连顺！
……
万万没想到，计划还是失败了，孔连顺化妆成小龙女，混在cosplay的队伍中逃出了字节跳动大街。只怪他的伪装太成功了，就是杨过本人来了也发现不了的！
请听题：给定 N（可选作为埋伏点的建筑物数）、 D（相距最远的两名特工间的距离的最大值）以及可选建筑的坐标，计算在这次行动中，大锤的小队有多少种埋伏选择。
注意：
两个特工不能埋伏在同一地点
三个特工是等价的：即同样的位置组合( A , B , C ) 只算一种埋伏方法，不能因“特工之间互换位置”而重复使用
数据范围： 0<n,d≤106 0 < n,d\le 10^6 \ 0<n,d≤106
输入描述:
第一行包含空格分隔的两个数字 N和D(1 ≤ N ≤ 1000000; 1 ≤ D ≤ 1000000)第二行包含N个建筑物的的位置，每个位置用一个整数（取值区间为[0, 1000000]）表示，从小到大排列（将字节跳动大街看做一条数轴）输出描述:
一个数字，表示不同埋伏方案的数量。结果可能溢出，请对 99997867 取模示例1
输入
4 3 1 2 3 4输出
4说明
可选方案 (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)示例2
输入
5 19 1 10 20 30 50输出
1说明
可选方案 (1, 10, 20)示例3
输入
2 100 1 102输出
0说明
无可选方案
import sys
"""
1、问题分析：要找到一个区间，这个区间内的最大值和最小值的差要在d之间，然后找到这个区间任意三个数组成排列之和
"""def solve():mod = 99997867n, d = map(int, sys.stdin.readline().split())positions = list(map(int, sys.stdin.readline().split()))res = 0 #答案left = 0 #窗口的左边界for right in range(len(positions)):#遍历右边界while positions[right] - positions[left] > d: #当窗口的最大值与最小值的差大于d时left += 1 #左边界收缩#用来计算窗口内满足条件的个数count = right - left#如果窗口里面刚好三个数或者没有三个数，只有一种方案，这里是2的原因是因为我们把下标0算进去了if count <= 2:res = 1#计算count里面选三个数的组合else:res += count * (count - 1) // 2res %= mod#防止答案越界print(res % mod)
solve()
3.雀魂启动
小包最近迷上了一款叫做雀魂的麻将游戏，但是这个游戏规则太复杂，小包玩了几个月了还是输多赢少。
于是生气的小包根据游戏简化了一下规则发明了一种新的麻将，只留下一种花色，并且去除了一些特殊和牌方式（例如七对子等），具体的规则如下：
- 总共有36张牌，每张牌是1~9。每个数字4张牌。
- 你手里有其中的14张牌，如果这14张牌满足如下条件，即算作和牌
- 14张牌中有2张相同数字的牌，称为雀头。
- 除去上述2张牌，剩下12张牌可以组成4个顺子或刻子。顺子的意思是递增的连续3个数字牌（例如234,567等），刻子的意思是相同数字的3个数字牌（例如111,777）
例如：
1 1 1 2 2 2 6 6 6 7 7 7 9 9 可以组成1,2,6,7的4个刻子和9的雀头，可以和牌
1 1 1 1 2 2 3 3 5 6 7 7 8 9 用1做雀头，组123,123,567,789的四个顺子，可以和牌
1 1 1 2 2 2 3 3 3 5 6 7 7 9 无论用1 2 3 7哪个做雀头，都无法组成和牌的条件。
现在，小包从36张牌中抽取了13张牌，他想知道在剩下的23张牌中，再取一张牌，取到哪几种数字牌可以和牌。
输入描述:
输入只有一行，包含13个数字，用空格分隔，每个数字在1~9之间，数据保证同种数字最多出现4次。输出描述:
输出同样是一行，包含1个或以上的数字。代表他再取到哪些牌可以和牌。若满足条件的有多种牌，请按从小到大的顺序输出。若没有满足条件的牌，请输出一个数字0示例1
输入
1 1 1 2 2 2 5 5 5 6 6 6 9输出
9说明
可以组成1,2,6,7的4个刻子和9的雀头示例2
输入
1 1 1 1 2 2 3 3 5 6 7 8 9输出
4 7说明
用1做雀头，组123,123,567或456,789的四个顺子示例3
输入
1 1 1 2 2 2 3 3 3 5 7 7 9输出
0说明
来任何牌都无法和牌备注:
请不要根据自己的常识为题目增加未提及的条件对于20%的数据，保证和牌时一定是4个刻子+雀头的形式
"""
1、问题分析：该题要我们思考我们要摸到什么样的牌才能拿够胡牌？
那么胡牌的条件是什么呢？题目给出了下面的描述:
4个顺子或者刻子 + AA的形式（A表示1-9）
那么我们就要考虑我选择哪张牌来当AA，同时因为涉及到数目和数字，我们用字典的形式来存储数据
"""
#当前的手牌能够胡牌
def is_win_hand(counter):#按照上面的逻辑，我们要选择一个雀头for num in range(1,10):#雀头的数量必须大于等于2if counter[num] >= 2:#我们用一个新的字典来存储雀头除去后的剩余刻子temp_counter = counter.copy()temp_counter[num] -= 2#看剩下的牌能不能够形成4个刻子if can_form_melds(temp_counter):return Truereturn False#看当前除去雀头的牌能不能形成四个刻子
def can_form_melds(counter):temp_counter = counter.copy()melds = 0#刻子的数量for num in range(1,10):#统计每张牌能够形成的刻子数量#形成AAA的刻子while temp_counter[num] >= 3:temp_counter[num] -= 3melds += 1#形成顺子类型的刻子if num <= 7:#只有小于7的牌能当顺子的开头while temp_counter[num] >= 1 and temp_counter[num + 1] >= 1 and temp_counter[num + 2] >= 1:temp_counter[num] -= 1temp_counter[num + 1] -= 1temp_counter[num + 2] -= 1melds += 1return melds == 4
def solve():from collections import defaultdicthand = list(map(int, input().split()))#用来记录我的牌是什么样的counter = defaultdict(int)for num in hand:counter[num] += 1#答案数组result = []#处理逻辑：我从1,10中加入一张牌看能不能胡牌for num in range(1,10):#同一数字的牌最多只能出现四张if counter[num] >= 4:continuetemp_counter = counter.copy()#将我摸到的牌加入我的牌里temp_counter[num] += 1#如果摸到的这张牌能够让我胡牌if is_win_hand(temp_counter):result.append(num)#如果没有可能胡牌了if not result:print(0)else:print(' '.join(map(str,sorted(result))))solve()
4.特征提取
小明是一名算法工程师，同时也是一名铲屎官。某天，他突发奇想，想从猫咪的视频里挖掘一些猫咪的运动信息。为了提取运动信息，他需要从视频的每一帧提取“猫咪特征”。一个猫咪特征是一个两维的vector<x, y>。如果x_1=x_2 and y_1=y_2，那么这俩是同一个特征。
因此，如果喵咪特征连续一致，可以认为喵咪在运动。也就是说，如果特征<a, b>在持续帧里出现，那么它将构成特征运动。比如，特征<a, b>在第2/3/4/7/8帧出现，那么该特征将形成两个特征运动2-3-4 和7-8。
现在，给定每一帧的特征，特征的数量可能不一样。小明期望能找到最长的特征运动。
输入描述:
第一行包含一个正整数N，代表测试用例的个数。每个测试用例的第一行包含一个正整数M，代表视频的帧数。接下来的M行，每行代表一帧。其中，第一个数字是该帧的特征个数，接下来的数字是在特征的取值；比如样例输入第三行里，2代表该帧有两个猫咪特征，<1，1>和<2，2> 所有用例的输入特征总数和<100000N满足1≤N≤100000，M满足1≤M≤10000，一帧的特征个数满足 ≤ 10000。 特征取值均为非负整数。输出描述:
对每一个测试用例，输出特征运动的长度作为一行示例1
输入
1 8 2 1 1 2 2 2 1 1 1 4 2 1 1 2 2 2 2 2 1 4 0 0 1 1 1 1 1 1输出
3说明
特征<1,1>在连续的帧中连续出现3次，相比其他特征连续出现的次数大，所以输出3
"""
1、问题分析：本题我们要找到一个出现次数最多的特征，其实就是统计每个特征连续出现的最大数量，那么我们要知道当前特征是不是连续的，就必须知道上一帧里面有没有这个特征
2.数据结构：我们用字典来存储特征以及出现的帧数，这样就可以知道当前特征有没有在上一帧出现过了
"""
def solve():import sys#读取所有输入的数据并按照空格分隔input = sys.stdin.read().split()#初始化指针ptr用于遍历输入列表ptr = 0#读取测试用例的数量NN = int(input[ptr])ptr += 1#读取每个测试用例for _ in range(N):#读取当前帧的特征个数M = int(input[ptr])ptr += 1#初始化最大特征运动长度max_lenmax_len = 0#用来记录上一帧中出现的特征last_seen = {}#处理每一帧数据for _ in range(M):#读取当前特征数量KK = int(input[ptr])ptr += 1#初始化列表freatures存储当前帧的所有特征features = []#读取当前帧下的所有特征for _ in range(K):x = int(input[ptr])y = int(input[ptr + 1])features.append((x,y))ptr += 2#处理当前特征temp = {}for feature in features:#处理特征列表中的每个特征if feature in last_seen: #如果特征在上一帧中出现过#连续次数+1temp[feature] = last_seen[feature] + 1else:#特征第一次出现temp[feature] = 1#处理完后更新最大数据if temp[feature] > max_len:max_len = temp[feature]#保存当前帧的信息作为下一帧的last_seenlast_seen = temp#输出最大长度print(max_len)
solve()
5.毕业旅行问题
小明目前在做一份毕业旅行的规划。打算从北京出发，分别去若干个城市，然后再回到北京，每个城市之间均乘坐高铁，且每个城市只去一次。由于经费有限，希望能够通过合理的路线安排尽可能的省一些路上的花销。给定一组城市和每对城市之间的火车票的价钱，找到每个城市只访问一次并返回起点的最小车费花销。
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 256M，其他语言512M
输入描述：
城市个数n（1<n≤20，包括北京）城市间的车票价钱 n行n列的矩阵 m[n][n]输出描述：
最小车费花销 s示例1
输入例子：
4 0 2 6 5 2 0 4 4 6 4 0 2 5 4 2 0输出例子：
13例子说明：
共 4 个城市，城市 1 和城市 1 的车费为0，城市 1 和城市 2 之间的车费为 2，城市 1 和城市 3 之间的车费为 6，城市 1 和城市 4 之间的车费为 5，依次类推。假设任意两个城市之间均有单程票可购买，且票价在1000元以内，无需考虑极端情况。
"""
方法思路：
1.问题分析：对于城市的履行方案，是有限个方案里面选最佳，所以我们可以采用动态规划来做
2.动态规划的状态定义：dp[mask][u],其中mask表示已经访问过的城市集合，u表示当前访问的城市
dp[mask][u]表示从城市u触发，经过mask表示的城市合集，最后回到起点的最小花费
3.状态转移：对于每一个状态(mask,u),遍历所有未访问的城市v,更新dp[mask | (1<<v)][v]
为dp[mask][u] + m[u][v]的最小值
4.初始化和结果:初始化时，dp[(1 << n) - 1][0](从起点北京出发，没有访问其他城市时我的花费0)
最终结果是dp[(1<<n)-1][0],访问其他节点回到起点的最小值
"""
def solve():import sysinput = sys.stdin.read().split() #读取所有输入数据并拆分成列表ptr = 0#初始化指针，用来逐个访问输入列表中的元素#读取城市数量nn = int(input[ptr])ptr += 1#初始化车票价格矩阵mm = []for _ in range(n):#读取每一行车票的价格，并转化为整数列表row = list(map(int, input[ptr:ptr + n]))m.append(row)ptr += n#初始化动态规划表dpsize = 1 << n #结算状态的总数，即2^nINF = float('inf')#dp[mask][u]表示在状态mask下，当前所在城市u的最小花费dp = [[INF] * n for _ in range(size)]#初始状态，从北京（城市0）出发，仅访问过北京dp[1][0] = 0 #动态规划填表过程for mask in range(size):#遍历所有可能的状态maskfor u in range(n): #遍历所有当前所在城市uif dp[mask][u] == INF: #如果当前状态不可以到达，跳过continuefor v in range(n): #遍历所有可能的下一城市vif not (mask & (1 << v)): #如果城市没有被访问过new_mask = mask | (1 << v) #更新状态，标记城市v已经被访问#新状态花钱少，选择新状态if dp[new_mask][v] > dp[mask][u] + m[u][v]:dp[new_mask][v] = dp[mask][u] + m[u][v]#计算回来的最小花费full_mask = (1 << n) - 1 #全访问状态，所有城市都已经被标记min_cost = INF #初始化最小花费为无穷大for u in range(1,n): #遍历除了北京以外的所有城市#计算从城市u回到北京的花费，并更新最小花费if dp[full_mask][u] + m[u][0] < min_cost:min_cost = dp[full_mask][u] +m[u][0]#答案print(min_cost)solve()
6.找零
Z国的货币系统包含面值1元、4元、16元、64元共计4种硬币，以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为N(0<N≤1024)N (0 < N \le 1024)N(0<N≤1024)的商品，请问最少他会收到多少硬币？
输入描述:
一行，包含一个数N。输出描述:
一行，包含一个数，表示最少收到的硬币数。示例1
输入
200输出
17说明
花200，需要找零824块，找12个64元硬币，3个16元硬币，2个4元硬币即可。
"""
1、问题分析：很典型的贪心问题，为了最小化我们取得的硬币数量，每次我们最好选择硬币面值最大的
"""
def solve(N):#需要找零的金额change = 1024 - N#定义硬币的面值，按照从大到小排序coins = [64,16,4,1]#最后答案count = 0for coin in coins:#检查当前剩余零钱是不是大于当前硬币面值if change >= coin:#计算当前change最多能换硬币的数量num = change // coin#将使用的硬币数量num加到总计数量count中count += num#更新剩余零钱的数量change -= num * coin#找零完成了，不用在找了if change == 0:breakreturn count
N = int(input())
print(solve(N))
7.机器人跳跃问题
机器人正在玩一个古老的基于DOS的游戏。游戏中有N+1座建筑——从0到N编号，从左到右排列。编号为0的建筑高度为0个单位，编号为i的建筑的高度为H(i)个单位。
起初， 机器人在编号为0的建筑处。每一步，它跳到下一个（右边）建筑。假设机器人在第k个建筑，且它现在的能量值是E, 下一步它将跳到第个k+1建筑。它将会得到或者失去正比于与H(k+1)与E之差的能量。如果 H(k+1) > E 那么机器人就失去 H(k+1) - E 的能量值，否则它将得到 E - H(k+1) 的能量值。
游戏目标是到达第个N建筑，在这个过程中，能量值不能为负数个单位。现在的问题是机器人以多少能量值开始游戏，才可以保证成功完成游戏？
输入描述:
第一行输入，表示一共有 N 组数据.第二个是 N 个空格分隔的整数，H1, H2, H3, ..., Hn 代表建筑物的高度输出描述:
输出一个单独的数表示完成游戏所需的最少单位的初始能量示例1
输入
5 3 4 3 2 4输出
4示例2
输入
3 4 4 4输出
4示例3
输入
3 1 6 4输出
3备注:
数据约束： 1 <= N <= 10^5 1 <= H(i) <= 10^5
"""
1、问题分析：能量的变化规律：如果当前能量为E，跳到高度为H（k+1）的建筑，新的能量
E_new为：
(1)如果H（k + 1）> E,则E_new = E - (H(k + 1) - E) = 2E - H(k + 1)
(2)如果H(k + 1) < E,则E_new = E + (E - H(k + 1)) = 2E - H(k + 1)
综上所述，无论怎么样，新的能量总是2E - H(k + 1)
但是在任何一个环节中都必须保证E_new > 0
2、解决思路：逆推，即我们在最后一个位置的时候能量刚好为0
"""
def solve():#数据读入import sysinput = sys.stdin.read().split()N = int(input[0])H = list(map(int, input[1:N+1]))#初始化能量E = 0，这是逆向计算的起点E = 0#逆向遍历所有建筑for i in range(N - 1, -1, -1):"""1、计算到达当前建筑i所需的最小能量2、这里加1是为了确保在奇数情况下能够向上取整"""E = (E + H[i] + 1) // 2print(E)solve()
题单总结
| 题目 | 核心考点 | 时间复杂度 | 空间复杂度 | 关键技巧 |
|---|---|---|---|---|
| 聪明的编辑 | 字符串处理 | O(n) | O(1) | 双指针（易） |
| 抓捕孔连顺 | 组合数学 | O(n) | O(1) | 滑动窗口（易） |
| 雀魂启动 | 回溯算法 | O(1) | O(1) | 模拟（中） |
| 特征提取 | 哈希表 | O(n) | O(n) | 滑动窗口（中） |
| 毕业旅行 | 状态压缩DP | O(n^2 * 2^n) | O(n*2^n) | 位运算（难） |
| 找零 | 贪心算法 | O(1) | O(1) | 数学计算（易） |
| 机器人跳跃 | 逆向思维 | O(n) | O(1) | 数学推导（中） |
这些题目涵盖了算法竞赛中的经典题型，考察了不同的解题思维和算法技巧。从字符串处理到动态规划，从数学推导到贪心选择，都是编程面试和算法竞赛中的常见考点。
解题模板
-
滑动窗口
常见问题类型及适用场景：
问题类型 判断条件 窗口调整策略 最小覆盖子串 包含所有目标字符 满足条件时收缩窗口 最长无重复子串 窗口内有重复字符 出现重复时收缩窗口 长度不超过K的最长子数组 窗口内元素和>K 超过阈值时收缩窗口 固定大小窗口问题 窗口大小固定 同步移动左右边界 """ 滑动窗口算法通用模板 :param nums:输入数组/字符串 :param target:目标值/条件 :return: 符合条件的结果 """ #初始化窗口边界和结果变量 left = 0 #窗口左边界 right = 0#窗口右边界 window = {}#用于记录窗口内元素的状态（根据需要选择合适的数据结构) result = 0#存储最终结果 vaild = 0#用于跟踪窗口内满足条件的元素数量（根据题目需求调整）#开始滑动窗口（外层循环移动右边界） while right < len(nums):#获取当前右边界元素c = nums[right]right += 1 #右边界向右移动#更新窗口内数据（根据题目需求修改）window[c] = window.get(c,0) + 1if window[c] == target:#示例条件：具体请根据题目修改vaild += 1#内层循环移动左边界（当窗口需要收缩时）while vaild > need:#示例收缩条件：实际请根据题目修改#获取当前元素左边界元素d = nums[left]left += 1#左边界向右移动#更新窗口内的数据if window[d] == target: #示例条件，根据实际需求进行修改vaild -= 1window[d] -= 1return result # ==================使用示例================ #示例1，最小覆盖子串问题 def min_window(s:str,t:str) -> str:"""找到s中包含t所有字符的最小子串:param:s:源字符串:param:t:目标字符集合:return:满足条件的最小字符串"""from collections import defaultdict#记录t中每个字符需要匹配的数量need = defaultdict(int)for c in t:need[c] += 1#初始化窗口指针和状态变量left,right = 0,0 window = defaultdic(int)vaild = 0start,length = 0,float('inf') #start为最小子串的起始下标，length为最小子串的长度#开始滑动窗口while right < len(s):#右移窗口的过程c = s[right]right += 1#更新窗口内的数据if c in need:window[c] += 1#当窗口内某个字符数量达到need的要求是，vaild+1if window[c] == need[c]:vaild += 1#判断左侧窗口是否要收缩（当窗口满足所有字符需要时）while vaild == len(need):#更新最小覆盖子串if right - left < length:start = leftlength = right - left#d是将要移除窗口的字符d = s[left]#窗口左移left += 1#更新窗口内的数据if d in need:#当窗口内某个字符的数量不在满足need的要求时，vaild -1if window[d] == need[d]:vaild -= 1window[d] -= 1return "" if length == float('inf') else s[start:start + length]def length_of_longest_substring(s:str)->int:"""找到不包含重复字符的最长子串长度:param s:输入字符串】:return:最长无重复子串的长度"""#初始化窗口指针和状态变量left,right = 0,0window = {}max_len = 0while right < len(s):c = s[right]window[c] += 1while window[c] > 1:d = s[left]window[d] -= 1left += 1max_len = max(max_len,right - left)return max_len -
动态规划
常见问题类型适配：
问题类型 状态定义 关键转移方程 斐波那契 dp[i]: 第i项的值 dp[i] = dp[i-1] + dp[i-2] 背包问题 dp[i][w]: 前i件物品重量w的最大价值 dp[i][w] = max(选/不选当前物品) 最长递增子序列 dp[i]: 以第i元素结尾的LIS长度 dp[i] = max(dp[j])+1 (j<i且nums[j]<nums[i]) 股票买卖问题 dp[i][k][0/1]: 第i天交易k次持有/不持有的最大收益 根据状态机转移
#自顶向下记忆化搜索模板
def dp_template_memoization(nums):"""自顶向下记忆化搜索模板:param nums:输入参数:return: 最优解"""from functools import lru_cache#使用装饰器自动实现备忘录功能(python 3.9+)@lru_cache(maxsize = None)def dfs(state):#边界条件处理if is_terminal_state(state):return base_case_value#遍历所有可能的选择min_res = float('inf') #求最小值问题初始化#max_res = -float('inf') #求最大值问题初始化for choice in get_available_choices(state):#状态转移new_state = state_transition(state,choice)#递归子问题subproblem = def(new_state)#根据问题类型更新结果min_res = min(min_res,cost(choice) + subproblem)#max_res = max(max_res,cost(choice) + subproblem)return min_res #或return max_res#从初始状态开始求解return dfs(initial_state)
# ===========斐波那契数列==========
@lru_cache(maxsize = None)
def fib(n):if n <= 1: return nreturn fib(n - 1) + fib(n - 2)
def dp_template_iterative(nums):"""自底向上迭代动态规划模板:param nums:输入餐宿:return :最优解"""n = len(nums)#1.定义dp数组/表(根据问题维度调整)#一维示例（斐波那契）dp = [0] * (n + 1)#二维示例（背包问题）# dp = [[o] * (capacity - 1) for _ in range(n + 1)]#2.初始化基础情况dp[0] = base_case_value_0dp[1] = base_case_value_1#3.状态转移（填表顺序很重要）for i in range(2,n + 1):#一维填写示例for j in range(1, i):#根据问题调整循环条件#状态转移方程dp[i] = min(dp[i],dp[j] + cost)#最小化问题#dp[i] = max(dp[i],dp[j] + value)#最大化问题#4.返回最终结果return dp[n]
# ==================使用示例：爬楼梯问题====================
def climb_stairs(n:int)->int:if n<= 2:return ndp = [0] * (n + 1)dp[1],dp[2] = 1,2for i in range(3,n + 1):dp[i] = dp[i - 1] + dp[i - 2]return dp[n]
def dp_essential_template(problem_input):"""动态规划四要素模板1.定义状态2.状态转移方程3.初始条件4.计算顺序"""#1.定义状态（DP数组的含义）#dp[i][j]表示...(根据具体的问题进行定义)#2.初始化基础情况dp = [[0] * cols for _ in range(rows)]dp[0][0] = base_values#3.状态转移（注意计算顺序）for i in range(rows): for j in range(cols):#根据状态转移方程更新if condition1:dp[i][j] = dp[i - 1][j] + value1elif condition2:dp[i][j] = min(dp[i][j - 1],dp[i - 1][j]) + value2#4.返回最终结果return dp[-1][-1]
# =====================使用示例：最长公共子序列===============
def longestCommonSubsequence(text1: str,text2: str) -> int:m,n = len(text1),len(text2)#1.定义dp数组：dp[i][j]表示text1前i个字符和text2前j个字符的LCS长度#使用(m + 1)*(n + 1)的二维数组（包含空字符串的情况)dp = [[0] * (n + 1) for _ in range(m + 1)]#2.初始化：第一行和第一列默认为0（空字符串和任何字符串的LCS都为0）#3.状态转移（按行填充）for i in range(1,m + 1):for j in range(1,n + 1):if text1[i - 1] == text2[j - 1]#LCS长度 = 左上角 + 1dp[i][j] = dp[i - 1][j - 1] + 1else: #当前字符串不匹配# LCS长度 = 上方或者下方的最大值dp[i][j] = max(dp[i-1][j],dp[i][j - 1])return dp[m][n]
最长公共子序列DP表（text1=“abcde”, text2=“ace”）
‘’ a c e ‘’ 0 0 0 0 a 0 1 1 1 b 0 1 1 1 c 0 1 2 2 d 0 1 2 2 e 0 1 2 3
