今天來看看另外幾個把數值放進狀態、並且帶有 LIS 色彩的動態規劃吧！

Exercise 30: Leetcode 403 - Frog Jump

題目連結

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

題目敘述

有一隻青蛙從河岸的某側想要跳到另一側。一開始他的跳躍能力是 1，位置在 0。接下來牠可以一路往右邊跳，如果前一跳的距離是 k 的話，那下一跳的距離可以是 k-1, k, 或 k+1。給定河中石頭的位置，請問青蛙能否跳到最右邊那顆石頭（代表另一側河岸）呢？

(示意圖請參考就好，我盡力了...)

解題思考

這題可以考慮二維動態規劃 dp(i, j) = true/false 代表青蛙是否可以跳到 j 這個位置，並且前一次落點在 i。有了這一跳，我們就可以試圖找出下一個落點 dp(i, j) → dp(j, k)：其中 stones[k] - stones[j] 的值會是 stones[j] - stones[i] + { -1, 0, 1 }。

我們在這邊提供另一個想法：我們可以讓 dp(j) 儲存一個「集合」，代表青蛙可以從 0 的位置跳到第 j 顆石頭，所有可能的前一步跳躍能力所成的集合。

參考程式碼 (Python3)

class Solution:
    def canCross(self, stones: List[int]) -> bool:
        dp = [set() for _ in range(len(stones))]
        dp[0] = set([0])
        for i in range(1, len(stones)):
            for j in range(0, i):
                d = stones[j] - stones[i]
                if (d in dp[j]) or (d+1 in dp[j]) or (d-1 in dp[j]):
                    dp[i].add(d)
        return bool(dp[len(stones)-1])

後話

這概念其實根本就是 BFS，但仔細想想，其實本質上 BFS 也是動態規劃的一種啊，只是你的目標函數定義是 true / false（到得了、或是到不了）。

Exercise 31: Leetcode 873 - Length of Longest Fibonacci Subsequence

題目連結

https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/

題目敘述

給你一個嚴格遞增序列 A，請找出最長的子序列使得他滿足費氏數列規則：(i) 至少有三項、(ii) 相鄰兩項加總之後等於緊鄰的下一項。

解題思考

這題與前一題概念相同，如果找到連續三項 A[i] + A[j] = A[k] 的話，我們可以從 dp(i, j) 把數值推入 dp(j, k)。

參考程式碼 (Python3)

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        pos = {A[i]:i for i in range(len(A))}
        dp = [[2] * len(A) for _ in range(len(A))]
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                if pos.get(A[i] + A[j]) != None:
                    k = pos[A[i]+A[j]]
                    dp[j][k] = max(dp[j][k], dp[i][j] + 1)
        v = max([max(row) for row in dp])
        return 0 if v <= 2 else v

接下來我們來討論一個筆者覺得要看出 dp 不是那麼容易（而且要證明也不是那麼容易）的題目。

Exercise 32: Leetcode 818 - Race Car

題目連結

https://leetcode.com/problems/race-car/

題目敘述

在一條數線上，你的賽車正在 0 點的位置，你的目標是 position。在每一個時刻，你有一個位置和一個速度。你一開始的速度是 "+1"。每個時間點，你可以選擇「A: 加速」或「R: 迴轉」。加速會讓你的位置變成 (當前的位置 + 當前速度)，而速度會在移動位置後變成兩倍。迴轉則不會改變你的位置，但你的速度會從正數變成 "-1" 或從負數變成 "+1"。

請找出抵達 position 的最短時間。

解題思考

考慮 dp(D) 代表你面向目標而且距離目標尚有 D 單位距離遠。首先我們要說明的事情是：在這種情況下，「迴轉」永遠不是一個必要的選擇。簡略說明如下：如果存在一個以 "R" 開頭的操作字串，那麼 (1) 我們可以找到下一個 R (因為目標在另一邊啊)，(2) 我們總能夠「偷天換日」把一開始的 R 到下一個 R 這段，直接補到整個序列最後面，仍然能到達目的地！

接下來，我們考慮序列一開始「向右行」然後「向左行」這兩段(AAA...ARAAA...AR)。如果走完這兩段以後，停下來的位置反而比一開始更遠了，那麼我們可以再次把這段踢到後面去XD

Case 1

因此！我們可以考慮動態規劃的規則是：加速、回頭、加速、回頭，然後距離更近了！第一段加速如果加了 i 次，那麼位移就是 X = 2^i - 1，如果第二段是 j 次，那麼位移就是 Y = 2^j - 1。這個「距離更近」可能有兩種情形：在終點左邊、或在終點右邊。

如果在終點右邊的話，就不需要回頭了，這樣子問題方向才是對的。

• 終點左邊：dp(D) ← dp(D - X + Y) + i + j + 2
• 剛好停在終點：dp(D) ← i + j + 1
• 終點右邊：dp(D) ← dp(|D - X + Y|) + i + j + 1 + (2 if Y > 0 else 0)

這個轉移要成立，必須要 |D-X+Y| ≤ D 才行唷。滿足這樣條件的 X 和 Y 不多呢，至多只有 log^2 D 種。

Case 2

另一種可能是一步登天，不用回頭直接到終點： dp(X) ← i。

於是我們就可以寫成程式碼囉！雖然 Case 1 還可以再變快一些(→ log D)，但至少能過了哈哈。

參考程式碼 (Python3)

class Solution:
    def racecar(self, target: int) -> int:
        dp = [sys.maxsize] * (target + 1)
        dp[0] = 0

        # Case 2 先處理
        dp[1] = 1
        x = 3
        while x <= target:
            dp[x] = dp[x//2] + 1
            x = x * 2 + 1

        # Case 1 再處理
        for D in range(2, target+1):
            for i in range(1, 16):
                for j in range(0, 16):
                    X = 2**i - 1
                    Y = 2**j - 1
                    if abs(D - X + Y) < D:
                        extra = 0
                        if D - X + Y > 0:
                            extra = 1
                        elif D - X + Y < 0:
                            extra = (2 if Y > 0 else 0)
                        dp[D] = min(dp[D], dp[abs(D-X+Y)] + i + 1 + j + extra)

        return dp[target]

我真的覺得這題是 Leetcode 少數不錯的動態規劃題～