题目：给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。每一步，你可以从下标 i 跳到下标：
i + 1 满足：i + 1 < arr.length
i - 1 满足：i - 1 >= 0
j 满足：arr[i] == arr[j] 且 i != j
请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。注意：任何时候你都不能跳到数组外面。
来源：https://leetcode-cn.com/problems/jump-game-iv/
法一： 自己的超时代码 dfs
思路：利用回溯的方法，把每次要遍历的记入k中，同时记录每个分支遍历过的索引，防止重复遍历，剪枝条件是：如果某次回溯的时候，某个到达个位置的次数大于之前记录的值了，直接结束回溯。这个题无法用dp，解题的时候要快速识别出无法用dp动态规划来解决。或即使用dp也很复杂。
from typing import List from collections import defaultdict from functools import lru_cache class Solution: def minJumps(self, arr: List[int]) -> int: # print('3333333333', len(arr)) d = defaultdict(list) size = len(arr) for i,j in enumerate(arr): d[j] = d[j] + [i] # @lru_cache(None) memo = defaultdict(lambda : size) def recursion(index, cou=0, used=[-1,0]): # 回溯结束条件 if index == size-1: # print('*' * 8, cou) return cou # 加上这个剪枝条件后，仍然超时 # 这个条件是如果现在的cou大于之前记录的值，则直接返回，结束这次回溯 if memo[index] < cou: print('-'* 30) return size # if index == 0: # k = [1] + d[arr[0]][1:] # # print('kkkkkkkkkkkkkkkkk') # else: # used [-1,0]的初始值中的-1是为了处理index=0时的情况 # 这儿之所以取set是因为有重复值的情况， k = list(set(([index-1] if index-1 not in used else []) + ([index+1] if index+1 not in used else []) + list(set(d[arr[index]]) - set(used)))) # 当k为空的时候说明，两边都走过了，也无法跳跃了，直接返回 if k == []: return cou memo[index] = cou res = size cou += 1 for j in k: # 这里是关键，每次回溯的时候，传递下一次要跳到的地方，跳过的步数，以及已经跳过的位置， # 如果没有这个used，程序会陷入死循环，实际上是为了防止重复遍历 res = min(res, recursion(j, cou=cou, used=used+[j])) return res return recursion(index=0) if __name__ == '__main__': duixiang = Solution() # a = duixiang.minJumps(arr = [100,-23,-23,404,100,23,23,23,3,404]) a = duixiang.minJumps(arr = [68,-94,-44,-18,-1,18,-87,29,-6,-87,-27,37,-57,7, 18,68,-59,29,7,53,-27,-59,18,-1,18,-18,-59,-1,-18, -84,-20,7,7,-87,-18,-84,-20,-27]) print(a)
法二：bfs 别人的代码
思路：这个题是一个非常典型的最短路径问题，天然具有应用bfs的优势，因为在这个最短路径问题中，每走一步都是在向目标靠近，而对于每个位置而言，从出发点第一次到达该位置的步数即到达该点的最小值，所以无需再次遍历，由此便想到用bfs，将要走的位置放在队列的前面，由此便控制住了步数，最先到达末尾的即最短的步数。
from collections import defaultdict from typing import List class Solution: def minJumps(self, arr: List[int]) -> int: d = defaultdict(list) n = len(arr) for i in range(n): d[arr[i]].append(i) vis = [0] * n vis[0] = 1 q = [(0, 0)] while q: # i是当前位置的索引，k是走过的步数， i, k = q.pop(0) # 遍历当前位置的上一个和下一个，以及可以跳跃的位置 for j in d[arr[i]] + [i - 1, i + 1]: # 如果出界或者已经遍历过了，直接进行下一个循环 if j < 0 or j >= n or vis[j]: continue # 一旦跳到最后一个位置了，则它即为最少的步数，直接返回结果 if j == n - 1: return k + 1 # 遍历过的标记为1 vis[j] = 1 # 把当前的位置放入队列，并且把步数加1 q.append((j, k + 1)) # 某个值的索引一旦遍历过其中一个后，就置为[]，因为其余的索引已经放入队列了，无需再次遍历 # 如果第二次在相同的值之间跳跃，则浪费了步数，肯定不是最短的 d[arr[i]] = [] return 0
ttt