Di bawah ini adalah deskripsi masalah, diikuti dengan solusi rekursifnya menggunakan Python. Solusi ini tidak efisien. Saya tahu menggunakan memoisasi, kami dapat meningkatkan solusi ini. Saya juga telah melalui pertanyaan serupa di StackOverflow tetapi saya tidak dapat menemukan solusinya. Saya cukup baru dalam teknik memoisasi. Jika ada yang bisa membantu saya dengan solusi menggunakan memoisasi, itu akan sangat membantu.

Deskripsi Masalah: Seekor katak sedang menyeberangi sungai. Sungai dibagi menjadi beberapa unit, dan di setiap unit, mungkin ada atau tidak ada batu. Katak dapat melompat di atas batu, tetapi tidak boleh melompat ke dalam air.

Diberikan daftar posisi batu (dalam satuan) dalam urutan menaik, tentukan apakah katak dapat menyeberangi sungai dengan mendarat di batu terakhir. Awalnya, katak berada di batu pertama dan menganggap lompatan pertama harus 1 unit.

Jika lompatan terakhir katak adalah k unit, lompatan berikutnya harus k - 1, k, atau k + 1 unit. Katak hanya bisa melompat ke arah depan.

Contoh

Di bawah ini adalah solusi saya menggunakan rekursi (Python).

class Solution:
    def canCross(self, stones: List[int]) -> bool:
            return self.helper(stones[0],stones,1)
            
    def helper(self,curr,stones,k):
        if curr+k == stones[-1]:
            return True
        
        if not curr+k in stones or k<=0: 
            return False
        else:
            curr = curr+k 
            return self.helper(curr,stones,k-1)  or self.helper(curr,stones,k) or self.helper(curr,stones,k+1)
0
Krishna 7 Januari 2021, 23:37

3 jawaban

Jawaban Terbaik

Ini dia versi memo yang lebih cepat, lebih cepat dari versi sebelumnya. Ini sekitar 50% lebih cepat...

class Solution:
    """
    """
    def canCross(self, stones: List[int]) -> bool:
        self.target = stones[-1]
        stones = set(stones)
        return self.dfs(stones, 0, 0, {})

    def dfs(self, stones, cur, k, memo):
        if cur == self.target:
            return True
        if (cur, k) in memo:
            return memo[(cur, k)]
        for nxt in [k-1, k, k+1]:
            if nxt > 0 and cur + nxt in stones:
                if self.dfs(stones, cur+nxt, nxt, memo):
                    memo[(cur, k)] = True
                    return True
        memo[(cur, k)] = False
        return False
0
Daniel Hao 7 Januari 2021, 21:56

@Krisna,

Silakan coba versi memo ini untuk melihat apakah itu mempercepat.


     def canCross(self, stones: List[int]) -> bool:
         if stones[1] != 1:
            return False
         d = {x: set() for x in stones}
         d[1].add(1)
         for x in stones[:-1]:
             for j in d[x]:
                 for k in range(j-1, j+2):
                     if k > 0 and x+k in d:
                         d[x+k].add(k)
         return bool(d[stones[-1]])
0
Daniel Hao 7 Januari 2021, 21:10

functools dekorator untuk memoisasi metode di kelas:

from functools import cached_property

class Solution:
    def canCross(self, stones: List[int]) -> bool:
            return self.helper(stones[0],stones,1)
    
    @cached_property
    def helper(self,curr,stones,k):
        if curr+k == stones[-1]:
            return True
        
        if not curr+k in stones or k<=0: 
            return False
        else:
            curr = curr+k 
            return self.helper(curr,stones,k-1)  or self.helper(curr,stones,k) or self.helper(curr,stones,k+1)

0
Gwang-Jin Kim 7 Januari 2021, 22:01