喜歡跳著寫的後果就是有時候會本末倒置，像今天終於看了前幾天逃避的 Memorization（記憶化搜索），結果發現應該擺在 DP 第一天的，不過就當個複習吧。

講到 memorization 經常會提到 recursion 和 iteration。iteration 就是進行重複的操作，像是做 DP 時依照規律把表格填滿那樣；recursion 則是重複呼叫某個東西，把大問題切小。用 Fibonacci 數列為例，recursion 是用 F(n) = F(n-1) + F(n-2) = [F(n-2)+F(n-3)] + [F(n-3)+F(n-4)] ... 這樣一副切下去，iteration 則是從 F(1) 開始往上一路算到 F(n)。

Memorizaion 基本上大概是 recursion 加上記憶功能，透過記錄遍歷過的狀態訊息，避免一再執行重複動作以降低複雜度。不過相對於 DP 的方法，因為一個狀態有可能被訪問多次（DP 一個狀態就是被計算一次），因此效率會比較低。

403. Frog Jump 這題寫起來挺直觀的，就是不停的紀錄當下的狀態，然後在動作的同時和歷史狀態做對照，確認最終有沒有辦法達到目標狀態。

class Solution:
    def canCross(self, stones: List[int]) -> bool:
        if stones[1] != 1:
            return False

        s = set(stones)
        visit = defaultdict(set)

        q = [[1,1]]
        final = stones[-1]
        nxt = [-1,0,1]

        while q:
            cur, step = q.pop(0)
            for i in nxt:
                tmp = step+i
                if tmp < 0:
                    continue
                    
                tmp2 = cur+tmp
                if tmp2 in visit and tmp in visit[tmp2]:
                    continue
                elif tmp2 == final:
                    return True
                elif tmp2 > final:
                    continue
                
                if tmp2 in s:
                    q.append([tmp2, tmp])
                    visit[tmp2].add(tmp)
        
        return False

附上 DP 版的解法，開 n^2 矩陣的話會爆時間，所以就用 hash table 來記了。

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

        dp = {stone: set() for stone in stones}
        dp[0].add(0)

        for i in range(n):
            for k in dp[stones[i]]:
                for step in [k - 1, k, k + 1]:
                    if step > 0 and stones[i] + step in dp:
                        dp[stones[i] + step].add(step)

        return bool(dp[stones[-1]])

• Memorization
  • 403. Frog Jump

• Total Count: 19