1차원 도로에서 자동차를 운전하고 있다고 가정해 보겠습니다. 현재 위치 =0이고 속도 =1입니다. 이 두 가지 작업 중 하나를 수행할 수 있습니다.
-
가속:위치:=위치 + 속도 및 속도:=속도 * 2역 기어:속도:=속도> 0일 때 속도> 0, 그렇지 않으면 속도:=1.
최소한 목표에 도달하는 데 필요한 이동 수를 찾아야 합니다.
따라서 입력이 target =10과 같으면 출력은 7이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
dfs() 함수를 정의합니다. 이것은 숫자, 비용, 위치, 음수, 대상을 취합니다.
-
tot :=비용 + 최대값 2 *(pos − 1) 및 2 * (neg − 1)
-
tot>=ans이면
-
반환
-
-
target이 0과 같으면
-
ans :=ans와 tot의 최소값
-
반환
-
-
단계 :=(2^digit) − 1
-
단계 * 2 <|target|이면
-
반환
-
-
dfs(숫자 - 1, 비용, 양수, 음수, 대상)
-
dfs(숫자 - 1, 비용 + 숫자, 위치 + 1, 음수, 목표 - 단계)
-
dfs(숫자 - 1, 비용 + 숫자 * 2, 위치 + 2, 음수, 목표 - 단계 * 2)
-
dfs(숫자 - 1, 비용 + 숫자, 양수, 음수 + 1, 대상 + 단계)
-
dfs(숫자 - 1, 비용 + 숫자 * 2, 양수, 음수 + 2, 대상 + 단계 * 2)
-
-
주요 기능에서 다음을 수행하십시오 -
-
ans :=무한대
-
안녕하세요 :=1
-
동안 2^hi
-
안녕 :=안녕 + 1
-
-
dfs(안녕하세요, 0, 0, 0, 대상)
-
반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution: def solve(self, target): self.ans = int(1e9) hi = 1 while (1 << hi) < target: hi += 1 self.dfs(hi, 0, 0, 0, target) return self.ans def dfs(self, digit, cost, pos, neg, target): tot = cost + max(2 * (pos − 1), 2 * neg − 1) if tot >= self.ans: return if target == 0: self.ans = min(self.ans, tot) return step = (1 << digit) − 1 if step * 2 < abs(target): return self.dfs(digit − 1, cost, pos, neg, target) self.dfs(digit − 1, cost + digit, pos + 1, neg, target − step) self.dfs(digit − 1, cost + digit * 2, pos + 2, neg, target − step * 2) self.dfs(digit − 1, cost + digit, pos, neg + 1, target + step) self.dfs(digit − 1, cost + digit * 2, pos, neg + 2, target + step * 2) ob = Solution() print(ob.solve(10))
입력
10
출력
7