-
Notifications
You must be signed in to change notification settings - Fork 116
Open
Description
递归代码模板
public void recur(int level,int param){
//terminator 递归终止条件
if(level > MAX_LEVEL){
return;
}
//process current level logic 处理当前层的逻辑
process(level,param);
//drill down 下钻
recur(level-+1,newParam);
//restore current status 状态恢复
}
分治
- 拒绝人肉递归
- 找到最近最简方法,将其拆解成可重复解决的问题
- 数学归纳法
本质:寻找重复性
代码模板
def divide_conquer(problem, param1, param2, ...):
# recursion terminator
if problem is None:
print_result
return
# prepare data
data = prepare_data(problem)
subproblems = split_problem(problem, data)
# conquer subproblems
subresult1 = self.divide_conquer(subproblems[0], p1, ...)
subresult2 = self.divide_conquer(subproblems[1], p1, ...)
subresult3 = self.divide_conquer(subproblems[2], p1, ...)
…
# process and generate the final result
result = process_result(subresult1, subresult2, subresult3, …)
# revert the current level states
动态规划
- 将复杂问题拆分为简单子问题
- 分治+最优子结构
Reactions are currently unavailable
Metadata
Metadata
Assignees
Labels
No labels