C++/Python DP動態規劃與二元搜尋解Leetcode難題403 Frog Jump

C++/Python DP動態規劃與二元搜尋解Leetcode難題403 Frog Jump
使用遞迴結合記憶法來解決。這就是動態規劃（DP）。由於石頭的位置是按照升序排列的，因此要找到下一個可以跳躍的石頭，可以使用二元搜尋。

 ------------------------

 Use recursion with meomory to solve. That is DP. Since stones is in ascending order, to find the next stone for jump is using binary search. 

[codes on Leecode]https://leetcode.com/problems/frog-jump/solutions/3964790/c-python-2d-dp-binary-search-vs-hash-table-beats-98-48/

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

        @cache
        def f(i, k):
            if i==n-1: return True
            if i>=n: return False
            ans=False
            for jump in [k-1, k, k+1]:
                if jump==0: continue
                next= bisect_left(stones[i+1:], stones[i]+jump)+(i+1)
                if next==n or stones[next]!=stones[i]+jump: continue
                ans = ans or f(next, jump)
            return ans
        
        return f(0, 0)