動態規劃算法的發現
1. 問題可分而治之且 BFS
首先, 問題必須是可分而治之的, 並在最後合併. 分而治之(遞歸)是爲了窮舉, 合併是爲了找最優.
Result r(costs[], target){ args = []; for(cost in costs){ tmp = r(costs - cost, target - cost) + cost; args += tmp; } return G(args); }
雖然上面的代碼是 DFS, 但形式上是 BFS, 而且也應該寫成 BFS, 只不過 BFS 的代碼不簡潔而已.
思考: 與貪婪算法的區別.
2. 合併函數 G(...) 可迭代處理
因爲 G() 是可以轉換成迭代的, 所以代碼變成:
Result r(costs[], target){ ret = PRE; for(cost in costs){ tmp = r(costs - cost, target - cost) + cost; ret = G(ret, tmp); } return ret; }
PRE(開始之前)是引入的邊界外的參數, 以便讓代碼處理邏輯簡化, 不然要加 if 條件判斷, 就無法在形式化上統一.
3. 增加緩存
Result r(costs[], target, dp){ cache_key = make_cache_key(costs, target); if(dp[cache_key]){ return dp[cache_key]; } ret = PRE; for(cost : costs){ tmp = r(costs - cost, target - cost, dp) + cost; ret = G(ret, tmp); } dp[cache_key] = ret; return ret; }
4. 將遞歸轉成迭代
#### 推導型
Result forward(costs, target){ init(dp); cc[PRE] = costs; for(curr in range(PRE, target)){ costs = cc[curr]; for(cost : costs){ dp[next] = G(dp[next], dp[curr] + cost); cc[next] = costs - cost if dp[next] updated; } } return dp[target]; }
#### 回溯型
Result backtrack(costs[], target){ dp[PRE] = PRE; cc[PRE] = costs; for(curr in range(atomic, target)){ for(prev in get_prev_list(curr)){ costs = cc[prev]; cost = costs.the_one(); // 只有唯一個cost能連通prev和curr dp[curr] = G(dp[curr], dp[prev] + cost); cc[curr] = costs - cost if dp[curr] updated; } } return dp[target]; }
5. 緩存可淘汰: 滑動窗口
這一條件不是必須的, 因爲很多動態規劃解法無法淘汰緩存. 如果緩存可淘汰, 而且是可以用滑動窗口的方式淘汰, 那麼就是非常**經典且巧妙的**動態規劃解法.
對於推導型動態規劃, 只需要緩存最長的推導距離. 對於回溯型動態規劃, 只需要緩存最長的回溯距離.