403. Frog Jump

[zeikar]

Problem link

https://leetcode.com/problems/frog-jump/

Problem Summary

처음엔 1칸을 뛸 수 있고 k칸 뛴 다음엔 k-1, k, k+1 칸을 뛸 수 있을 때 끝까지 점프할 수 있는지 확인하는 문제.

Solution

그냥 DP. N 크기도 작아서 대충 돌려주면 된다. 하드 중에서 아주 쉬운 문제.

DP[i, k]: i 인덱스에서 k칸 뛸 때의 가능 여부

위처럼 점화식 세우고 k-1,k,k+1 에 대해 돌려주면 된다. 위치가 아니라 인덱스로 저장했는데 map을 쓰면 위치로도 풀 수 있긴 하다.

Source Code

from functools import lru_cache
from typing import List


class Solution:
    def canCross(self, stones: List[int]) -> bool:

        @lru_cache(None)
        def jump(idx, k):
            if idx == len(stones) - 1:
                return True

            i = idx + 1
            while i < len(stones) and stones[i] - stones[idx] < k - 1:
                i += 1
            while i < len(stones) and k + 1 >= stones[i] - stones[idx]:
                if jump(i, stones[i] - stones[idx]):
                    return True
                i += 1

            return False

        return jump(0, 0)