递归相关（分治，回溯，动态规划）

[hankviv]

斐波拉契数列带缓存操作：

var fibMap = make(map[int]int)

func fib(n int) int {
    if n == 1 {
        return 0
    }
    if n == 2 {
        return 1
    }
    if res, ok := fibMap[n]; ok {
        return res
    }
    fibn := fib(n-1) + fib(n-2)
    fibMap[n] = fibn
    return fibn
}

递推写法：

func fib(n int) int {
    if n <= 1 {
        return n
    }
    res := make([]int, n+1)
    res[0], res[1] = 0, 1
    for i := 2; i <= n; i++ {
        res[i] = (res[i-1] + res[i-2])
    }
    return res[n]
}

[hankviv]

动态规划 Dynamic Programming

• 动态规划就是动态的递推
• 相当于 分治 + 最优解
• 如果有最优子结构，就是动态规划 否则就是分治。
• 动态规划会淘汰掉其他，只处理最优解。

[hankviv]

回溯模版 一把梭 相关问题
78. 子集

//闭包写法
func subsets(nums []int) [][]int {
    //结果集初始化
    res := [][]int{}
    //当前决策队列
    path := []int{}
    //是否需要标记已使用
    //例如 used := make(map[int]bool) map来标记是否使用
    //当前使用index来标记 每次+1

    var backTrack func(nums []int,index int,path []int)
    backTrack = func(nums []int, index int, path []int) {
    //判断结果集是否是想要的 如果是 就加入结果集,当前需要决策树每个历史 所以不需要判断
    if true{
        temp := make([]int,len(path))
        copy(temp,path)
        res = append(res,temp)
    }
        for i:= index; i< len(nums); i++{
            path = append(path,nums[i])
            backTrack(nums,i+1,path)
            path = path[:len(path) -1]
        }
    }
    backTrack(nums,0,path)
    return res
}

//全局变量写法 模版

var res [][]int
func subsets(nums []int) [][]int {
    //结果集初始化
    res = [][]int{}
    //每次决策队列
    path := []int{}
    //是否需要标记已使用
    //例如 used := make(map[int]bool) map来标记是否使用
    //当前使用index来标记 每次+1
    backTrack(nums,0,path)
    return res
}

func backTrack(nums []int,index int,path []int)  {
    //判断结果集是否是想要的 如果是 就加入结果集,当前需要决策树每个历史 所以不需要判断
    if true{
        temp := make([]int,len(path))
        copy(temp,path)
        res = append(res,temp)
    }
    for i:= index; i< len(nums); i++{
        path = append(path,nums[i])
        backTrack(nums,i+1,path)
        path = path[:len(path) -1]
    }
}