基礎——アルゴリズム

5つのアルゴリズムはここから来ています
ぶんかつアルゴリズム
分けて治す:直接解決しにくい大きな問題を、いくつかの規模の小さい同じ問題に分割して、それぞれを破壊して、分けて治す.
分割法には、各階層の再帰に3つのステップがあります.

step1   ：              ，    ，            ；

step2   ：                  ，           

step3   ：                。

その中の最後のステップは、統合であり、分治アルゴリズムの特徴である.一般的に動的に計画すればいいです.
ダイナミックプランニング
特徴:サブ問題の解には重複部分があり,中間結果はcacheできる.逆押し.keys:状態変数,中間結果,遷移方程式
動的計画には、各階層の再帰に2つのステップがあります.

step1        

step2       

テンプレート:

ArrayList> totalResult \\    

void DP(map, intermediateResult, currentState){
if(currentState==  ){
       = new(intermediateResult) \\for safety
  totalResult.add(     )
  }
 else{
  //     .....
 intermediateResult.add()
 DP(map, intermediateResult, NextState)
 intermediateResult.remove() //     ，  remove
 //     ....
 }
}

欲張りアルゴリズム
特徴:貪欲法は一般的に最適な問題を解くために用いられ、実際には問題の状態空間ツリーを検索し、この状態空間ツリーの中で最適な経路を検索して最適な戦略を求める.貪欲法は上から下まで深さ探索のみを行い,その代価はサブ問題の数,すなわち木の高さに依存し,現在の問題の状態で毎回選択されるのは1であり,すなわち,実際には広さ探索を行わないため,得られる解が必ずしも最適解ではなく,近似最適解である可能性が高いという欠点をもたらした.
さかのぼる
https://segmentfault.com/a/1190000006121957特徴:ステータス空間ツリーで深さ検索を行い、広さ検索を行います.key:決定関数テンプレート:

     finalResult;
void backTracking(intermediateResult, state){
if(    )
    return ;
if(intermediateResult      ){
    finalResult.add(intermediateResult)
    return finalResult;
}
for(    ){//    
 backTracking(intermediateResult,nextState);//    
}
return ;
}