2016 ?summer &
1、遞歸與分治法
遞歸的基本思想：一個直接或間接調(diào)用自身的算法
（1）斐波那契數(shù)列:
分治法的基本思想：將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題相同舰蟆。遞歸地解決這些子問題秕豫，然后將各子問題的解合并得到原問題的解奢浑。
（1）排列問題：
先貼出可能用到的代碼：
交換兩個數(shù)的模板：
問題：已知R={1,2,3},對它產(chǎn)生全排列
分析：當(dāng)?shù)谝粋€數(shù)1固定慎陵，對23進(jìn)行全排列，可以分為當(dāng)2固定马胧，對3進(jìn)行全排列；當(dāng)3固定衔峰，對2進(jìn)行全排佩脊，則可以得到123,132;其余當(dāng)?shù)谝粋€數(shù)是2，對13進(jìn)行全排列垫卤；當(dāng)?shù)谝粋€數(shù)是3威彰，對12進(jìn)行全排列。
程序代碼：
（2）整數(shù)劃分問題
問題：
程序代碼：
（3）二分搜索技術(shù)：
問題：給定已排好序的n個元素a[0,n-1],現(xiàn)要在這n個元素中找出一特定元素x
程序代碼：
循環(huán)實現(xiàn)：
遞歸實現(xiàn)：
（4）棋盤覆蓋
先貼出可能用到的代碼：
動態(tài)申請一個一維數(shù)組：
動態(tài)開辟一個二維數(shù)組：
問題：
分析：可以用分治法解決此問題葫男，當(dāng)k > 0時抱冷，將2^k * 2^k的棋盤分割為4個2^(k-1) * 2^(k-1)個子棋盤，如下圖：
上圖中的右圖就是我們填L型骨牌的方式梢褐，使得每一個區(qū)域都有一個特殊方格旺遮。
（5）合并排序
基本思想：當(dāng)n=1時赵讯，終止排序；否則將待排序的元素分割為大小大致相同的兩個子集和耿眉，分別對子集和進(jìn)行排序边翼，最終將排好序的子集和合并。
（6）快速排序
注：若數(shù)據(jù)是基本有序的鸣剪，則快速排序的效率不高组底，可以用隨機化法解決：
（7）線性時間選擇
問題：給定線性序集中n個元素和一個整數(shù)k，要求找出這n個元素中第k小的元素筐骇。
分析：利用分治法债鸡，調(diào)用Partition函數(shù)可以對其進(jìn)行劃分，一次劃分得到第pos個小的元素铛纬，然后判斷k值與pos的大小厌均，分別對部分重復(fù)上述步驟，最主要的是pos的求法是index-left+1
2告唆、動態(tài)規(guī)劃算法
基本思想：將待求解的問題分解為若干個子問題棺弊，先求解子問題，然后從這些子問題得到原問題的解擒悬。經(jīng)動態(tài)規(guī)劃法得到的子問題往往不是相互獨立的模她，為了避免重復(fù)計算，我們可以用一個表來記錄所有已解決的子問題的答案懂牧。它常用于求解具有最優(yōu)子結(jié)構(gòu)性質(zhì)（問題的最優(yōu)解包含了子問題的最優(yōu)解）和子問題重疊性質(zhì)（在用遞歸算法自頂向下的解決問題時侈净，每次產(chǎn)生的子問題并不總是新問題，有些問題被反復(fù)計算多次）的問題归苍。
基本步驟：a用狱、找出最優(yōu)解的性質(zhì)，并刻畫其特征拼弃；
b夏伊、遞歸地定義最優(yōu)值；
c吻氧、以自底向上的方式計算出最優(yōu)值溺忧；
d、根據(jù)計算最優(yōu)值時得到的信息盯孙，構(gòu)造一個最優(yōu)解鲁森。
（1）矩陣連乘問題
兩個矩陣相乘代碼：
問題：給定n個矩陣{A1，A2振惰，A3.........An}歌溉，計算出n個矩陣連乘積的最優(yōu)計算次序
分析：
a、最優(yōu)解的性質(zhì)：設(shè)A[1,n]是n個矩陣的連乘，則可將其劃分為A[1,k]和A[k+1,n]
b痛垛、遞歸地定義最優(yōu)值：設(shè)m[i,j]為所需的最少數(shù)乘次數(shù)草慧，則當(dāng)i=j時，m[i,j]=0匙头；當(dāng)i<j時漫谷，
m[i,j] = min(m[i,k]+m[k+1,j]+p[i-1]*p[k]*p[j]),其中k取值范圍是i到j(luò)-1；
c蹂析、以自底向上計算最優(yōu)值
d舔示、構(gòu)造一個最優(yōu)解
（2）最長公共子序列
規(guī)定：子序列是按照下標(biāo)遞增的方式
問題：給定兩個序列分別是：X={A,B,C,B,D,A,B},Y={B,D,C,A,B,A},假設(shè)Z是X和Y的最長公共子序列，求Z电抚？
分析：
a惕稻、最優(yōu)解的性質(zhì)：若xm = yn，則zk = xm = yn蝙叛，z(k-1)是x(m-1)和y(n-1)的最長公共子序列缩宜；若xm!=yn且zk!=xm，則z是x(m-1)和yn的最長公共子序列甥温；若xm!=yn且zk!=yn，則z是xm和y(n-1)的最長公共子序列妓布；
b姻蚓、遞歸地定義最優(yōu)值：用c[i][j]記錄xi和yj最長公共子序列的長度。當(dāng)i=j=0時匣沼，c[i][j]=0;當(dāng)i,j>0時狰挡，若xi=yj,則c[i][j]=c[i-1][j-1]+1;若xi!=yj,則c[i][j] =max(c[i][j-1],c[i-1][j])。
c释涛、以自底向上計算最優(yōu)值
d加叁、構(gòu)造一個最優(yōu)解
（3）0-1背包問題
問題：
分析：
a、最優(yōu)解的性質(zhì)：假設(shè)對于n元0-1向量x={x1,x2……xn}唇撬，有Sum(wi xi) <= c && Max(Sum(vi xi))為最優(yōu)解它匕，則有對于x={x2……xn}，有Sum(wi xi) - w1 x1 <= c && Max(Sum(vi xi)-v1 x1)為最優(yōu)解
b窖认、遞歸地定義最優(yōu)值：設(shè)m(i,j)代表最大價值豫柬，i表示為i……n,即放入了這么些物品，j代表當(dāng)前容器的容量扑浸。則有第一種情況當(dāng)i==n烧给，如果j>w[n]，則返回v[n],否則返回0喝噪；第二種情況當(dāng)i < n時础嫡，若jw[i],則返回Max( m(i+1,j) , (m(i+1,j-w[i]) + v[i] ) )
c、以自底向上計算最優(yōu)值：
d酝惧、構(gòu)造一個最優(yōu)解：
3榴鼎、回溯法
基本思想：它是將問題的所有解羅列出來伯诬，然后構(gòu)建一顆并非真實存在的解空間樹，并對這顆樹進(jìn)行深度優(yōu)先搜索檬贰。這里介紹兩種常用的解空間樹姑廉，當(dāng)所給的問題是從n個元素的集合中找出滿足某種性質(zhì)的子集時，這時的樹成為子集樹翁涤；當(dāng)所給的問題是確定n個元素滿足某種性質(zhì)的排列時桥言，這時的樹成為排列樹。
（1）求一個數(shù)組的子集
（2）n后問題
在一個n*n的象棋盤上擺放n個皇后葵礼，使其不可以相互攻擊号阿，即使她們不能處在同一行、同一列鸳粉、統(tǒng)一對角線上扔涧。
遞歸：
非遞歸：
思想：一列列地填，并判斷位置是否合法
結(jié)果：
拓展思維：
? ? ? ? ? ? ? ? ? ? ? ? ?----------------end -----
