递归、动态规划程序模板

递归代码模板

public  int  recur (int level, int param){

// 1 终止条件
  if (level > maxindex){
    return xxx;
  }
  
 //2 处理当前层 中的数据 
 process(level,param);
  
  //3 去到下一层递归
  
  recur (level+1 , param);
  
  //4 可能 ：如果恢复当前参数的状态，用的少
  }

 分治的模板 
 
 1 终止条件
 
 2 拆分子问题
 
 3 处理子问题 ，调用递归函数
 
 4 合并 子问题
 

动态规划 dp
动态规划 和递归或者分治 没有根本的区别（关键看有无最优子结构）

共性 ：找到 重复子问题


差异性 ：最优的结构、中途可以淘汰次优解