Skip to content

【0097_Week05】学习总结 #1272

@JiangJiang77

Description

@JiangJiang77

递归代码模板

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 状态恢复
}

分治

  1. 拒绝人肉递归
  2. 找到最近最简方法,将其拆解成可重复解决的问题
  3. 数学归纳法

本质:寻找重复性
代码模板

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

动态规划

  1. 将复杂问题拆分为简单子问题
  2. 分治+最优子结构

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions