今天來看看另外幾個把數值放進狀態、並且帶有 LIS 色彩的動態規劃吧！
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 顆石頭，所有可能的前一步跳躍能力所成的集合。
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（到得了、或是到不了）。
https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/
給你一個嚴格遞增序列 A，請找出最長的子序列使得他滿足費氏數列規則：(i) 至少有三項、(ii) 相鄰兩項加總之後等於緊鄰的下一項。
這題與前一題概念相同，如果找到連續三項 A[i] + A[j] = A[k] 的話，我們可以從 dp(i, j) 把數值推入 dp(j, k)。
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 不是那麼容易（而且要證明也不是那麼容易）的題目。
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
因此！我們可以考慮動態規劃的規則是：加速、回頭、加速、回頭，然後距離更近了！第一段加速如果加了 i 次，那麼位移就是 X = 2^i - 1，如果第二段是 j 次，那麼位移就是 Y = 2^j - 1。這個「距離更近」可能有兩種情形：在終點左邊、或在終點右邊。
如果在終點右邊的話，就不需要回頭了，這樣子問題方向才是對的。
這個轉移要成立，必須要 |D-X+Y| ≤ D 才行唷。滿足這樣條件的 X 和 Y 不多呢，至多只有 log^2 D 種。
另一種可能是一步登天，不用回頭直接到終點： dp(X) ← i。
於是我們就可以寫成程式碼囉！雖然 Case 1 還可以再變快一些(→ log D)，但至少能過了哈哈。
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 少數不錯的動態規劃題～
818Case1的|D-X+Y| ≤ D，我們是不是已經假設dp只會從離終點距離更小的情況更新？這樣我們怎麼考慮停下來的位置反而比一開始更遠了的情況呢？
在 Case 1 之前我們已經假設了不會有 "停下來的位置反而比一開始更遠" 的狀況出現了(換句話說, 我們不考慮這樣的解, 原因是我們總可以找到一條相同或甚至更短的序列來達到目標)
我試著證明這個但是感覺沒什麼思路的說。。。因為跑到另一邊距離更遠有時候用的步數有時比轉向跑到距離同樣遠更少，並不能併入到轉向的情況。。。
嗯...想了一陣之後我覺得「只需要考慮 |D-X+Y| <= D」這個敘述的確少了一些證明...我再想想看，謝謝你!
iThome鐵人賽
看影片追技術