本文主要作為自己的學(xué)習(xí)筆記黍匾，并不具備過多的指導(dǎo)意義。
暴力遞歸
把問題轉(zhuǎn)化為規(guī)目遄浚縮小了的同類問題的子問題
-
有明確的不需要繼續(xù)遞歸的條件
base case
求n!的結(jié)果
非遞歸版本
從非依賴關(guān)系入手哎迄。明確的知曉n!=1×2×3×...×n，然后按照順序編寫算法即可
func getFactorial1(n : Int) -> Int {
var res = 1
for i in 1..<n+1 {
res = res * i
}
return res
}
遞歸版本
從依賴關(guān)系入手境钟。n已知，嘗試解決(n-1)!
func getFactorial2(n : Int) -> Int {
if n == 1 {
return 1
}
return n * getFactorial2(n: n-1)
}
漢諾塔問題
打印N層漢諾塔從最左邊移動到最右邊的全部過程
每次一個俭识，不能打壓小只能小壓大
在第N層的問題上慨削，需要完成以下三個狀態(tài)：
第N層的完成依賴N-1的完成，而第N-1層的完成又依賴N-1層的完成套媚。
/// 移動1-N層漢諾塔
///
/// - Parameters:
/// - n: 需要移動到的層數(shù)
/// - form: 從哪根開始
/// - to: 從哪根結(jié)束
/// - help: 空那根
func hanoiGame(n : Int ,form :String ,to :String ,help :String) {
if n == 1 {//只移動第一層缚态，直接移動即可
print("Move 1 from " + form + " to " + to)
}else {
hanoiGame(n: n-1, form: form, to: help, help: to) //將第 1到n-1 層移動到 中間
print("Move \(n) " + "from " + form + " to " + to) //將第 n 層移動到 最右
hanoiGame(n: n-1, form: help, to: to, help: form) //將第 1到n-1 層移動到 最右
}
}
hanoiGame(n: 3, form: "左", to: "右", help: "中")
//打印
Move 1 from 左 to 右
Move 2 from 左 to 中
Move 1 from 右 to 中
Move 3 from 左 to 右
Move 1 from 中 to 左
Move 2 from 中 to 右
Move 1 from 左 to 右
打印字符串能組成的所有字串
輸入abc
打印：abc堤瘤，ab玫芦，ac，a本辐，bc桥帆，b，c
將字符串轉(zhuǎn)化成數(shù)組师郑，每個位置都有兩個選擇：打印&&跳過环葵。以此遞歸
代碼
func printStr(str :String) {
printAllSub(str: wordToArr(word: str), i: 0, res: "")
}
func printAllSub(str :[String] ,i :Int ,res :String) {
if i == str.count {
print(res)
}else {
printAllSub(str: str, i: i+1, res: res+str[i]) //打印當(dāng)前位置
printAllSub(str: str, i: i+1, res: res) //不打印當(dāng)前位置
}
}
func wordToArr(word:String) -> Array<String> {
var res : [String]
res = Array.init()
if word.count == 0 {
return res
}
let string = (word as NSString)
for i in 0..<string.length {
res.append(string.substring(with: NSMakeRange(i, 1)))
}
return res
}
母牛數(shù)目問題
有一頭母牛，它每年年初生一頭小母牛宝冕。每頭小母牛從第四個年頭開始张遭，每年年初也生一頭小母牛。請編程實現(xiàn)在第n年的時候地梨，共有多少頭母牛菊卷？
當(dāng)思維不夠直觀的時候，不妨列舉一下試試查找規(guī)律
F(N) = F(N-1) + F(N-3)
第五年 = 第四年存活的 + A與第二年出生的B所生的兩個
需要注意：如果N-3為負數(shù)則不用計算宝剖，只計算母牛自己生的一個即可
func func(n : Int) -> Int {
if n == 1 {
return 1
}
if n - 3 <= 0 {
return func1(n: n-1) + 1
}else {
return func1(n: n-1) + func1(n: n-3)
}
}
二維數(shù)組--從左上角到右下角最大值
只能向右或向下走
經(jīng)典的動態(tài)規(guī)劃題目洁闰，但我們可以先從遞歸做起
/// 二維數(shù)組--從左上角到右下角最大值
///
/// - Parameters:
/// - matrix: 二維矩陣
/// - x: x軸坐標(biāo)
/// - y: y軸坐標(biāo)
/// - Returns: 當(dāng)前點到右下角最小距離
func walk(matrix : [[Int]] ,x :Int ,y :Int) -> Int {
if (x == matrix.count-1) && (y == matrix[0].count-1) { //已經(jīng)到最后
return matrix[x][y] //返回當(dāng)前節(jié)點
}
if x == matrix.count-1 { //已經(jīng)到x軸末尾
return matrix[x][y] + walk(matrix: matrix, x: x, y: y+1) //當(dāng)前節(jié)點+y軸下一位
}
if y == matrix[0].count-1 { //已經(jīng)到y(tǒng)軸末尾
return matrix[x][y] + walk(matrix: matrix, x: x+1, y: y) //當(dāng)前節(jié)點+x軸下一位
}
//當(dāng)前節(jié)點+min(x軸下一位,y軸下一位)
return matrix[x][y] + min(walk(matrix: matrix, x: x+1, y: y), walk(matrix: matrix, x: x, y: y+1))
}
暴力遞歸的弊端
第一次進入walk(0,0)時，將會遞歸調(diào)用藍色位置walk(1,0)與walk(0,1)万细。
而在進入walk(1,0)時扑眉，又將遞歸調(diào)用walk(2,0)與walk(1,1)
并且進入walk(0,1)時，又將遞歸調(diào)用walk(0,2)與walk(1,1)
此時walk(1,1)將會執(zhí)行兩次赖钞，其之后的遞歸計算也指數(shù)級的重復(fù)腰素。
這就是動態(tài)規(guī)劃的意義，解決暴力遞歸重復(fù)執(zhí)行的缺點進行優(yōu)化
動態(tài)規(guī)劃
所有的動態(tài)規(guī)劃雪营，都是從暴力遞歸嘗試優(yōu)化(減少重復(fù)計算)而來
面試中弓千，對于一個沒有見過的動態(tài)規(guī)劃。我們可以先寫出一個遞歸的嘗試版本献起，在驗證正確性之后嘗試改成動態(tài)規(guī)劃洋访。
遞歸方法的后效性
如上文中所提到的暴力遞歸的弊端一樣：有些暴力遞歸會存在重復(fù)狀態(tài)镣陕，并且這些重復(fù)狀態(tài)的結(jié)果與到達其的路徑無關(guān)(狀態(tài)的參數(shù)確定，返回值則確定)姻政。
什么樣的問題可以改成動態(tài)規(guī)劃
對于無后效性遞歸呆抑，可以改成動態(tài)規(guī)劃的版本。
也有反例：比如漢諾塔問題扶歪，每一步打印都會對整體的打印結(jié)果造成影響理肺。就叫有后效性遞歸摄闸，無法進行動態(tài)規(guī)劃善镰。
無后效性遞歸如何改成動態(tài)規(guī)劃的通用方法
以二維數(shù)組--從左上角到右下角最大值題目為例：
-
分析可變參數(shù)，建立狀態(tài)表
以每個狀態(tài)的return結(jié)果建立一個二維數(shù)組年枕。
-
找到自己需要的最終狀態(tài)位置(0,0)
image -
回到base case 中炫欺，對不被依賴的位置進行設(shè)置
image -
對普遍位置進行設(shè)置
image 最終得到目標(biāo)位置
數(shù)組中元素是否能組成指定的和
先寫一個正常的暴力遞歸嘗試版本，與之前打印字符串能組成的所有字串的問題基本一致
/// 數(shù)組中元素是否能組成指定的和
///
/// - Parameters:
/// - arr: 數(shù)組
/// - i: 當(dāng)前位置
/// - sum: 已經(jīng)求的和
/// - aim: 目標(biāo)和
/// - Returns: 結(jié)果
func isSum(arr :[Int] ,i :Int ,sum :Int ,aim :Int) -> Bool {
if i == arr.count { //數(shù)組末尾已經(jīng)嘗試結(jié)束
return aim==sum //直接比對
}
let useC = isSum(arr: arr, i: i+1, sum: sum+arr[i], aim: aim) //嘗試添加當(dāng)前位置
let unuseC = isSum(arr: arr, i: i+1, sum: sum, aim: aim) //不添加當(dāng)前位置
return useC || unuseC
}
如何轉(zhuǎn)變成動態(tài)規(guī)劃
-
簡化表達式熏兄，并建立動態(tài)規(guī)劃表
只有兩個可變參數(shù)品洛，可以簡化成
F(i,sum)DP表的設(shè)計行為sum（最后一位為所有元素之和)，列為i摩桶。
在代碼上桥状，將作為一個二維數(shù)組存在
image -
確定目標(biāo)位置
image -
base case中找到不被依賴的位置
只有在F(N,Aim)時，aim==sum才會返回true
image -
對普遍位置進行設(shè)置
某一個位置F(i,sum1)的狀態(tài)依賴于F(i+1,sum1)與F(i+1,sum1)+arr[i]
而F(i+1,sum1)+arr[i]又作為新的sum值Sum2存在于DP表內(nèi)硝清。
兩個位置有一個為Aim辅斟，則將返回true
image 推回到最初位置
