bfsをDPの替わりとして使う
概要
- 最短経路、最小の組み合わせ等を求める際に、DPが適応例になる場合でもbfsで解くことができる
- 枝刈り等が必要になる場合はある
具体例
- リストがあり、リストの値分ジャンプできる時、最短、何回ジャンプすることで末尾に到達できるかの計算
def solve(nums):
ans = -1
que = collections.deque([(0, 0)])
head = -1
while que:
ptr, count = que.popleft()
# headに満たないものは枝刈りする
if head >= ptr:
continue
head = max(ptr, head)
if ptr >= len(nums)-1:
ans = count
break
v = nums[ptr]
for nptr in range(ptr+1, ptr+v+1):
que.append((nptr, count+1))
return ans
assert solve(nums = [2,3,1,1,4]) == 2
assert solve(nums = [2,3,0,1,4]) == 2
assert solve(nums = [1,2,3]) == 2