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
    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions