class Solution:
def movesToMakeZigzag(self, nums: List[int]) -> int:
if len(nums) == 1: return 0
dp = [0 for _ in range(len(nums))]
N = len(nums)
for idx in range(len(nums)):
prevNum = nums[idx-1] if idx - 1 >= 0 else float('inf')
nextNum = nums[idx+1] if idx + 1 < N else float('inf')
minNum = min(prevNum, nextNum)
if (prevNum <= 1000 or nextNum <= 1000) and minNum > nums[idx]:
dp[idx] = dp[idx-2] if idx - 2 >= 0 else 0
else:
dp[idx] = dp[idx-2] + nums[idx] - (minNum - 1) if idx - 2 >= 0 else nums[idx] - (minNum - 1)
return min(dp[-1], dp[-2])
일단 숫자를 움직일 때 숫자를 작게 하는 방법 밖에 없다는 사실을 잊으면 안된다.
각 인덱스의 값이 근접한 두 값보다 작게 만드는 방식으로 알고리즘을 구현하였습니다.
index
가 근접하는 숫자보다 작은 경우index
가 근접하는 숫자보다 작은 경우두가지 경우의 수를 나누어서 계산해야 하므로 각 dp에 값을 저장할때 index-2
자리의 값을 이용하여 현재 index
값을 결정합니다.
nums
의 길이가 1인 경우는 항상 0을 리턴합니다.
그렇기 않을 경우 dp[-1]
과 dp[-2]
중에 작은 값을 리턴하면 됩니다.