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. 缓存可淘汰: 滑动窗口
这一条件不是必须的, 因为很多动态规划解法无法淘汰缓存. 如果缓存可淘汰, 而且是可以用滑动窗口的方式淘汰, 那么就是非常 ** 经典且巧妙的 ** 动态规划解法.
对于推导型动态规划, 只需要缓存最长的推导距离. 对于回溯型动态规划, 只需要缓存最长的回溯距离.
来源: http://www.tuicool.com/articles/7ZnqU3Q