# 动态规划算法的发现

### 1. 问题可分而治之且 BFS

Result r(costs[], target){
args = [];
for(cost in costs){
tmp = r(costs - cost, target - cost) + cost;
args += tmp;
}
return G(args);
}

### 2. 合并函数 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];
}