本文主要作为自己的学习笔记，并不具备过多的指导意义。
暴力递归
-
把问题转化为规模缩小了的同类问题的子问题
-
有明确的不需要继续递归的条件
base case
求n!的结果
非递归版本
从非依赖关系入手。明确的知晓n!=1×2×3×...×n，然后按照顺序编写算法即可
func getFactorial1(n : Int) -> Int { var res = 1 for i in 1.. 递归版本
从依赖关系入手。n已知，尝试解决(n-1)!
func getFactorial2(n : Int) -> Int { if n == 1 { return 1 } return n * getFactorial2(n: n-1)}复制代码 打印N层汉诺塔从最左边移动到最右边的全部过程
每次一个，不能打压小只能小压大
在第N层的问题上，需要完成以下三个状态：
第N层的完成依赖N-1的完成，而第N-1层的完成又依赖N-1层的完成。
/// 移动1-N层汉诺塔////// - Parameters:/// - n: 需要移动到的层数/// - form: 从哪根开始/// - to: 从哪根结束/// - 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
将字符串转化成数组，每个位置都有两个选择：打印&&跳过。以此递归
代码
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]) //打印当前位置 printAllSub(str: str, i: i+1, res: res) //不打印当前位置 }}func wordToArr(word:String) -> Array { var res : [String] res = Array.init() if word.count == 0 { return res } let string = (word as NSString) for i in 0.. 母牛数目问题
有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？
当思维不够直观的时候，不妨列举一下试试查找规律
F(N) = F(N-1) + F(N-3)
第五年 = 第四年存活的 + A与第二年出生的B所生的两个
需要注意：如果N-3为负数则不用计算，只计算母牛自己生的一个即可
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) }}复制代码 二维数组--从左上角到右下角最大值
只能向右或向下走
经典的动态规划题目，但我们可以先从递归做起
/// 二维数组--从左上角到右下角最大值////// - Parameters:/// - matrix: 二维矩阵/// - x: x轴坐标/// - y: y轴坐标/// - Returns: 当前点到右下角最小距离func walk(matrix : [[Int]] ,x :Int ,y :Int) -> Int { if (x == matrix.count-1) && (y == matrix[0].count-1) { //已经到最后 return matrix[x][y] //返回当前节点 } if x == matrix.count-1 { //已经到x轴末尾 return matrix[x][y] + walk(matrix: matrix, x: x, y: y+1) //当前节点+y轴下一位 } if y == matrix[0].count-1 { //已经到y轴末尾 return matrix[x][y] + walk(matrix: matrix, x: x+1, y: y) //当前节点+x轴下一位 } //当前节点+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)时，将会递归调用蓝色位置walk(1,0)与walk(0,1)。
而在进入walk(1,0)时，又将递归调用walk(2,0)与walk(1,1) 并且进入walk(0,1)时，又将递归调用walk(0,2)与walk(1,1)
此时walk(1,1)将会执行两次，其之后的递归计算也指数级的重复。
这就是动态规划的意义，解决暴力递归重复执行的缺点进行优化
动态规划
所有的动态规划，都是从暴力递归尝试优化(减少重复计算)而来
面试中，对于一个没有见过的动态规划。我们可以先写出一个递归的尝试版本，在验证正确性之后尝试改成动态规划。
递归方法的后效性
如上文中所提到的暴力递归的弊端一样：有些暴力递归会存在重复状态，并且这些重复状态的结果与到达其的路径无关(状态的参数确定，返回值则确定)。
什么样的问题可以改成动态规划
对于无后效性递归，可以改成动态规划的版本。
也有反例：比如汉诺塔问题，每一步打印都会对整体的打印结果造成影响。就叫有后效性递归，无法进行动态规划。
无后效性递归如何改成动态规划的通用方法
以二维数组--从左上角到右下角最大值题目为例：
-
分析可变参数，建立状态表
以每个状态的return结果建立一个二维数组。
-
找到自己需要的最终状态位置(0,0)
-
回到base case 中，对不被依赖的位置进行设置
-
对普遍位置进行设置
-
最终得到目标位置
数组中元素是否能组成指定的和
先写一个正常的暴力递归尝试版本，与之前打印字符串能组成的所有字串的问题基本一致
/// 数组中元素是否能组成指定的和////// - Parameters:/// - arr: 数组/// - i: 当前位置/// - sum: 已经求的和/// - aim: 目标和/// - Returns: 结果func isSum(arr :[Int] ,i :Int ,sum :Int ,aim :Int) -> Bool { if i == arr.count { //数组末尾已经尝试结束 return aim==sum //直接比对 } let useC = isSum(arr: arr, i: i+1, sum: sum+arr[i], aim: aim) //尝试添加当前位置 let unuseC = isSum(arr: arr, i: i+1, sum: sum, aim: aim) //不添加当前位置 return useC || unuseC}复制代码 如何转变成动态规划
-
简化表达式，并建立动态规划表
只有两个可变参数，可以简化成
F(i,sum)DP表的设计行为sum（最后一位为所有元素之和)，列为i。 在代码上，将作为一个二维数组存在
-
确定目标位置
-
base case中找到不被依赖的位置 只有在F(N,Aim)时，
aim==sum才会返回true -
对普遍位置进行设置 某一个位置
F(i,sum1)的状态依赖于F(i+1,sum1)与F(i+1,sum1)+arr[i]而F(i+1,sum1)+arr[i]又作为新的sum值Sum2存在于DP表内。 两个位置有一个为Aim，则将返回true -
推回到最初位置